Computing $\sum_{i=0}^{\infty}\frac{i}{2^{i+1}}$ 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$$
 A: 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.
A: 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).
A: 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}$$
A: $$\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$$
A: 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}.
$$
