Take the 2-minute tour ×
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.

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

2 Answers 2

up vote 2 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|improve this answer
Thank you very much. –  Jessica Dec 29 '12 at 20:49

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|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!) 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? –  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.