Proving the infinite sum of $1/2^i$ without induction Prove 
$$\sum_{i=1}^n \frac{i}{2^i} = 2-\frac{n+2}{2^n} $$
Pretty trivial to do with induction, but as a practice problem for solving recurrences we have to do this only by repeating $\sum_{i=1}^n (1/2^i) = 1-1/2^n$ and summing the diagonals of the resulting lower triangular matrix.
So for example the first few rows of the matrix..
$1/2$
$1/2^2, 1/2 ^2$
$1/2^3, 1/2 ^3, 1/2^3$
.....
$1/2^n, .............1/2 ^n$
When you sum the diagonals you get $\sum_{k=1}^n (\sum_{i=k}^n 1/2^i)$, but this is basically back where we started. Now what?
 A: You have
$$ \sum_{i=k}^n (1/2)^{i} = \frac{(1/2)^{k}-(1/2)^{n+1}}{1-1/2} = (1/2)^{k-1}-(1/2)^n $$
Then the outer sum is
$$ \sum_{k=1}^n \left( (1/2)^{k-1}-(1/2)^n \right) = - n (1/2)^n + \sum_{k=1}^{n} (1/2)^{k-1} = - n (1/2)^n + \frac{1-(1/2)^n}{1-1/2} = 2 - \frac{n+2}{2^n} $$
A: $$\begin{align}
\sum_{i=1}^n \frac{1}{2^i} &= \frac12 + \left(\frac12\right)^2+ \left(\frac12\right)^3+\cdots + \left(\frac12\right)^n\\
\frac12 \sum_{i=1}^n \frac{1}{2^i} &= 0 + \left(\frac12\right)^2+ \left(\frac12\right)^3+\cdots + \left(\frac12\right)^n+\left(\frac12\right)^{n+1}
\end{align}$$
Subtracting these we see 
$$\begin{align}
\frac12 \sum_{i=1}^n \frac{1}{2^i} &= \frac12-\left(\frac12\right)^{n+1}
\end{align}$$
from which 
$$\begin{align}
\sum_{i=1}^n \frac{1}{2^i} &= 1-\left(\frac12\right)^{n}
\end{align}$$
Similarly, 
$$\begin{align}
\sum_{i=k}^n \frac{1}{2^i} &= \left(\frac12\right)^{k-1}-\left(\frac12\right)^{n}
\end{align}$$
Then, perform the outer sum similarly for the first term (i.e., sum a geometric progression).
A: Although Chappers' answer is good, an alternative approach might be to consider $$\sum_{i=1}^{n} \frac{x^i}{2^i}$$ which you can express with the usual formula for a geometric sum. Then if you take the derivative of both expressions and evaluate them at $x=1$, you will get the same answer without any induction.
