Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
See my answer in your other problem, i.e. break up the sum into pieces over which the floor takes on different integer values. – Ron Gordon Dec 29 '12 at 19:30
up vote 3 down vote accepted

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}$$



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

share|cite|improve this answer
Thank you very much. – Jessica Dec 29 '12 at 20:49

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*}


  • 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.

share|cite|improve this answer
This is great, especially the Knuth paper referenced, which was very interesting – tenCupMaximum Apr 12 at 2:28
@ChristianBurke: Thanks for your nice comment. You might be interested to look at these book recommendations: answer1 and answer2. Regards, – Markus Scheuer Apr 12 at 10:00

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

share|cite|improve this answer
Could you please give me more details on how to do the second term? I am not experienced at all with this. – Jessica Dec 29 '12 at 19:50
@Jessica no problem, I'll expand the answer above. – Tom Oldfield Dec 29 '12 at 19:57
@Jessica just added some more, hope that what I've put up above is both useful and correct. – Tom Oldfield Dec 29 '12 at 20:18
Thank 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!) (page 5) but I don't really understand how, they must have skipped a lot of steps. Perhaps you could, please, take a look? – Jessica Dec 29 '12 at 20:20
@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$ – Tom Oldfield Dec 29 '12 at 20:45

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.