Tuesday, November 28, 2017

sequences and series - Infinite sum of floor functions



I need to compute this (convergent) sum
$$\sum_{j=0}^\infty\left(j-2^k\left\lfloor\frac{j}{2^k}\right\rfloor\right)(1-\alpha)^j\alpha$$
But I have no idea how to get rid of the floor thing. I thought about some variable substitution, but it didn't take me anywhere.



Answer



We'll let $M=2^k$ throughout.



Note that $$f(j)=j-M\left\lfloor\frac{j}{M}\right\rfloor$$



is just the modulus operator - it is equal to the smallest positive $n$ such that $j\equiv n\pmod {M}$



So that means $f(0)=0, f(1)=1,...f(M-1)=M-1,$ and $f(j+M)=f(j)$.



This means that we can write:




$$F(z)=\sum_{j=0}^{\infty} f(j)z^{j}= \left(\sum_{j=0}^{M-1} f(j)z^{j}\right)\left(\sum_{i=0}^\infty z^{Mi}\right)$$



But $$\sum_{i=0}^\infty z^{Mi} = \frac{1}{1-z^{M}}$$



and $f(j)=j$ for $j=0,...,2^k-1$, so this simplifies to:



$$F(z)=\frac{1}{1-z^{M}}\sum_{j=0}^{M-1} jz^j$$



Finally, $$\sum_{j=0}^{M-1} jz^j = z\sum_{j=1}^{M-1} jz^{j-1} =z\frac{d}{dz}\frac{z^M-1}{z-1}=\frac{(M-1)z^{M+1}-Mz^{M}+z}{(z-1)^2}$$




So:



$$F(z)=\frac{(M-1)z^{M+1}-Mz^{M}+z}{(z-1)^2(1-z^{M})}$$



Your final sum is: $$\alpha F(1-\alpha)$$ bearing in mind, again, that $M=2^k$


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...