2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See my answer in your other problem, i.e. break up the sum into pieces over which the floor takes on different integer values. $\endgroup$ – Ron Gordon Dec 29 '12 at 19:30
4
$\begingroup$

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$

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is great, especially the Knuth paper referenced, which was very interesting $\endgroup$ – quietContest Apr 12 '16 at 2:28
  • $\begingroup$ @ChristianBurke: Thanks for your nice comment. You might be interested to look at these book recommendations: answer1 and answer2. Regards, $\endgroup$ – Markus Scheuer Apr 12 '16 at 10:00
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Could you please give me more details on how to do the second term? I am not experienced at all with this. $\endgroup$ – Jessica Dec 29 '12 at 19:50
  • $\begingroup$ @Jessica no problem, I'll expand the answer above. $\endgroup$ – Tom Oldfield Dec 29 '12 at 19:57
  • $\begingroup$ @Jessica just added some more, hope that what I've put up above is both useful and correct. $\endgroup$ – Tom Oldfield Dec 29 '12 at 20:18
  • $\begingroup$ 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? $\endgroup$ – Jessica Dec 29 '12 at 20:20
  • $\begingroup$ @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$ $\endgroup$ – Tom Oldfield Dec 29 '12 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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