Infinite sum of floor functions

Question

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 1

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$

Answer 2

Hint: break the sum up into

$$\sum_{j=0}^\infty j(1-\alpha)^j\alpha + \sum_{j=0}^\infty\left(-2^k\left\lfloor\frac{j}{2^k}\right\rfloor\right)(1-\alpha)^j\alpha$$

The sum on the left is easy to compute, and you can split the sum on the right up into the regions where $\lfloor\frac{j}{2^k}\rfloor$ takes different values.

For $0\leq j\leq2^k-1$, $\lfloor\frac{j}{2^k}\rfloor = 0$. For $2^k \leq j \leq 2^k+(2^k-1) = 2\times2^k - 1$, $\lfloor\frac{j}{2^k}\rfloor = 1$. Similarly, for any positive integer $m$, for $m2^k \leq j \leq (m+1)2^k -1$, $\lfloor\frac{j}{2^k}\rfloor = m$.

Using this we can split the left sum into

$$-\alpha2^k\sum_{m=0}^\infty \sum_{j=m2^k}^{(m+1)2^k-1}m(1-\alpha)^j = -\alpha2^k\sum_{m=0}^\infty m(1-\alpha)^{m2^k} \sum_{j=0}^{2^k-1}(1-\alpha)^j $$ $$=-\alpha2^k\sum_{m=0}^\infty m(1-\alpha)^{m2^k} \frac{(1-\alpha)^{2k}-1}{-\alpha} =2^k((1-\alpha)^{2k}-1)\sum_{m=0}^\infty m((1-\alpha)^{2k})^m$$

$$=\frac{2^k((1-\alpha)^{2k}-1)(1-\alpha)^{2k}}{((1-\alpha)^{2k}-1)^2} = \frac{-2^k(1-\alpha)^{2k}}{(1-\alpha)^{2k}-1}$$

( I think!)