<s>[INST] 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$$
 [/INST] $$\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$$
</s>