Computing $\sum_{i=0}^{\infty}\frac{i}{2^{i+1}}$

Question

I came across this while trying to solve Google's boys & girls problem, and although I know now it's not the right approach to take, I'm still interested in summing $\sum_{i=0}^{\infty}\frac{i}{2^{i+1}}$. Apparently it should be 1..but I'm having a tough time seeing this, especially since $\sum_{i=0}^{\infty}\frac{1}{2^{i+1}}=1$. I know it's a little elementary.. but I just can't figure out where I'm going wrong..

$$\sum_{i=0}^{\infty}\frac{i}{2^{i+1}} =\frac{1}{2}\sum_{i=0}^{\infty}\frac{i}{2^{i}} =\frac{1}{2}\sum_{j=0}^{\infty}\sum_{i=j}^{\infty}\frac{1}{2^{i}} =\frac{1}{2}\sum_{j=0}^{\infty}\left(\sum_{k=0}^{\infty}\frac{1}{2^{k}} - \sum_{i=0}^{j-1}\frac{1}{2^{i}}\right) =\frac{1}{2}\sum_{j=0}^{\infty}\left(2 - \frac{1-\frac{1}{2^j}}{1/2}\right)$$ $$=\frac{1}{2}\sum_{j=0}^{\infty}\left(2\frac{1}{2^j}\right)=2 \ne1$$

Answer 1

Your second equality is wrong. Actually it holds: $$ \frac 1 2\sum_{i=0}^{\infty}\frac{i}{2^{i}} = \frac 1 2 \sum_{j=0}^{\infty}\sum_{i=j+1}^{\infty}\frac{1}{2^{i}} = \frac 1 4 \sum_{j=0}^{\infty}\sum_{i=j}^{\infty}\frac{1}{2^{i}} $$ (there is $j+1$ instead of $j$ below the second sum sign on the RHS).

Answer 2

One way goes like this: \begin{align} & \sum_{i=0}^\infty \frac{i}{2^{i+1}} = \frac 1 4\sum_{i=1}^\infty i x^{i-1} \text{ (where $x=1/2$)} \\[10pt] = {} & \frac 1 4 \sum_{i=1}^\infty\frac{d}{dx} x^i = \frac 1 4 \frac{d}{dx}\sum_{i=1}^\infty x^i = \frac 1 4 \frac{d}{dx} \frac{x}{1-x} \end{align} and then do the differentiation and then plug in $x=1/2$. Notice we had to change $i=0$ to $i=1$.

One thing is problematic about this. The derivative of the sum of a finite number of functions is just the sum of their derivatives. But here we pulled $d/dx$ out of a sum with infinitely many terms. It doesn't always work when there are infinitely many, and this argument, as written here, doesn't explain why this is a case in which it does work.

Here's another way: \begin{array}{ccccccccccccc} i=0: \\[6pt] i=1: & & & \frac 1 4 \\[6pt] i=2: & & + & \frac 1 8 & + & \frac 1 8 \\[6pt] i=3: & & + & \frac 1 {16} & + & \frac 1 {16} & + & \frac 1 {16} \\[6pt] i=4: & & + & \frac 1 {32} & + & \frac 1 {32} & + & \frac 1 {32} & + & \frac 1 {32} \\[6pt] i=5: & & + & \cdots & \cdots & \cdots & & \cdots & & \cdots & \cdots \end{array} Now find the sum of each vertical column. Each one is a geometric series. Then find the sum of those sums, also a geometric series.

Answer 3

$$\begin{align} \frac{1}{4}&=1-\frac{3}{4}\\ \frac{1}{4} + \frac{2}{8} &= 1-\frac{4}{8}\\ \frac{1}{4}+\frac{2}{8} +\frac{3}{16}&= 1-\frac{5}{16} \end{align} $$

Therefore, try to show that $\frac{n}{2^{n+1}} = \frac{n+1}{2^n}-\frac{n+2}{2^{n+1}}$. That's pretty easy, so this is a telescoping sum:

$$\left(\frac{1}{1}-\frac{2}{2}\right) + \left(\frac{2}{2}-\frac{3}{4}\right)+\left(\frac{3}{4}-\frac{4}{8}\right)+\left(\frac 48-\frac5{16}\right)\dots$$

Answer 4

This may in some way be similar to some of answers given above.

$$\begin{align} S&=\sum_{i=0}^{\infty}\frac i{2^{i+1}}&&=\frac0{2^1}+\frac1{2^2}+\frac2{2^3}+\frac3{2^4}+\cdots+\frac i{2^{i+1}}+\cdots\\ 2S& &&=\frac1{2^1}+\frac2{2^2}+\frac3{2^3}+\cdots+\frac i{2^{i}}+\frac {i+1}{2^{i+1}}\cdots\\ \text{Subtracting,}\\ 2S-S& &&=\frac1{2^1}+\frac1{2^2}+\frac1{2^3}+\cdots+\frac 1{2^{i}}+\frac 1{2^{i+1}}\cdots\\ \therefore S&=\sum_{i=0}^{\infty}\frac i{2^{i+1}} &&=\frac{\frac12}{1-\frac12}\\ & &&=1\qquad \blacksquare \end{align}$$

Answer 5

OK, just for fun let's try another argument.

Throw a die repeatedly, each time getting one of the numbers $1,2,3,4,5,6$, and stop the first time a "$1$" appears.

On average, how many tosses does it take to get a $1$?

Intuitively, you'll probably guess that it's $6$. You might toss the die $30$ times before you get a $1$, but that happens very rarely.

The probability that you get a $1$ the first time is $1/6$.

The probability that you first get a $1$ the second time is $(5/6)(1/6)$.

The probability that you first get a $1$ the third time is $(5/6)^2(1/6)$.

The probability that you first get a $1$ the fourth time is $(5/6)^3(1/6)$.

The probability that you first get a $1$ the fifth time is $(5/6)^4(1/6)$.

$\ldots$ and so on. So the average number of times you toss the die to get a $1$ is

$$ \begin{array}{cccl} & 1 & \times & 1/6 \\ + & 2 & \times & (5/6)(1/6) \\ + & 3 & \times & (5/6)^2 (1/6) \\ + & 4 &\times & (5/6)^3(1/6) \\ + & 5 & \times & (5/6)^4 (1/6) \\ + & \cdots & & \cdots \cdots \\[10pt] \end{array} $$ \begin{align} = \frac 1 6 \sum_{i=1}^\infty i\left(\frac 5 6 \right)^{i-1}. \end{align} Hence that sum should be $6$.

Now do the same with a coin, tossing it until the first time "H" appears. The average number of tosses needed is $$ 2 = \sum_{i=1}^\infty i\left(\frac 1 2 \right)^i. $$

Consequently, $$ 1 = \sum_{i=1}^\infty i \left( \frac 1 2 \right)^{i+1}. $$