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.
Infinite sum of floor functions
-
0See my answer in your other problem, i.e. break up the sum into pieces over which the floor takes on different integer values. – 2012-12-29
3 Answers
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}
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.
-
1This is great, especially the Knuth paper referenced, which was very interesting – 2016-04-12
-
0@ChristianBurke: Thanks for your nice comment. You might be interested to look at these book recommendations: *[answer1](http://math.stackexchange.com/questions/954522/big-list-of-serious-but-fun-unusual-books/981590#981590)* and *[answer2](http://math.stackexchange.com/questions/742083/book-on-combinatorial-identities/748850#748850)*. Regards, – 2016-04-12
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!)
-
0Could you please give me more details on how to do the second term? I am not experienced at all with this. – 2012-12-29
-
0@Jessica no problem, I'll expand the answer above. – 2012-12-29
-
0@Jessica just added some more, hope that what I've put up above is both useful and correct. – 2012-12-29
-
0Thank you very much. It's very surprising though, not what I expected. In the meantime I found out that sombody has solved exactly this (weirdly!) http://ipnpr.jpl.nasa.gov/progress_report/42-159/159E.pdf (page 5) but I don't really understand how, they must have skipped a lot of steps. Perhaps you could, please, take a look? – 2012-12-29
-
0@Jessica It's a very similar argument, just without explanation. The key difference is that they writer of the article has kept the two sums together, because in this case, it can make things a bit easier. Also note that "their" $\alpha$ is $1-$ "your" $\alpha$ – 2012-12-29
-
0That's fantastic, thank you. – 2012-12-29