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$
1
  • $\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, 2012 at 19:30

3 Answers 3

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$
0
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$
2
  • 1
    $\begingroup$ This is great, especially the Knuth paper referenced, which was very interesting $\endgroup$ Apr 12, 2016 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$
    – epi163sqrt
    Apr 12, 2016 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$
6
  • $\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, 2012 at 19:50
  • $\begingroup$ @Jessica no problem, I'll expand the answer above. $\endgroup$ Dec 29, 2012 at 19:57
  • $\begingroup$ @Jessica just added some more, hope that what I've put up above is both useful and correct. $\endgroup$ Dec 29, 2012 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, 2012 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$ Dec 29, 2012 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.