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.

Solutions Collecting From Web of "Infinite sum of floor functions"

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$

Note: This answer uses Iverson brackets to cope with the floor function. Although this may need some more lines, the calculations are easy and can be performed this way more or less mechanically. The answer was inspired by example (1.14) of Two Notes on Notation by D. Knuth.

For convenience only we set $N=2^k$. We obtain

\begin{align*}
\sum_{j=0}^{\infty}&\left(j-N\left\lfloor\frac{j}{N}\right\rfloor\right)(1-\alpha)^j\alpha=\\
&=\alpha\sum_{j=0}^{\infty}\sum_m(j-Nm)(1-\alpha)^j\left[m=\left\lfloor\frac{j}{N}\right\rfloor\right]\tag{1}\\
&=\alpha\sum_{j=0}^{\infty}\sum_m(j-Nm)(1-\alpha)^j\left[m\leq \frac{j}{N}<m+1\right]\tag{2}\\
&=\alpha\sum_{j=0}^{\infty}\sum_m(j-Nm)(1-\alpha)^j\left[Nm\leq j <N(m+1)\right]\\
&=\alpha\sum_{m=0}^{\infty}\sum_{j=Nm}^{N(m+1)-1}(j-Nm)(1-\alpha)^j\tag{3}\\
&=\alpha\sum_{m=0}^{\infty}\sum_{j=0}^{N-1}j(1-\alpha)^{j+Nm}\\
&=\alpha\left({\sum_{m=0}^{\infty}(1-\alpha)^{Nm}}\right)\left(\sum_{j=0}^{N-1}j(1-\alpha)^j\right)\\
&=\frac{\alpha}{1-(1-\alpha)^N}\left({\sum_{j=0}^{N-1}j(1-\alpha)^j}\right)\\
&=-\frac{\alpha}{1-(1-\alpha)^N}\frac{d}{d\alpha}\left(\sum_{j=0}^{N-1}j(1-\alpha)^{j-1}\right)\\
&=-\frac{\alpha}{1-(1-\alpha)^N}\frac{d}{d\alpha}\frac{1-(1-\alpha)^N}{\alpha}\\
&=-\frac{\alpha}{1-(1-\alpha)^N}\left[\frac{N(1-\alpha)^{N-1}}{\alpha}-\frac{1-(1-\alpha)^N}{\alpha^2}\right]\\
&=\frac{1-\alpha}{\alpha}-\frac{N(1-\alpha)^N}{1-(1-\alpha)^N}
\end{align*}

Comment:

  • In (1) we immediately get rid of the floor function and shift it into the logical statement within the Iverson brackets. We introduce thereby a new variable $m$ and use it to sum over the complete range of integers.

  • In (2) we use the relationship $x\leq \lfloor x\rfloor < x+1$ to further simplify things

  • In (3) we exchange the sums and restrict the limits of $j$ and $m$ accordingly. So, we don’t need the Iverson brackets any longer and the following is routine work.

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!)