# How to prove $\sum\limits_{i=0}^{n-1}\frac{i}{2^i} = 2 - \frac{n + 1}{2^{n-1}}$ by induction?

I'm practicing mathematical induction for a discrete math exam. The concept of proving by induction by proving that closedForm(n-1) + sumEquation(n) = closedForm(n) makes sense, but I'm having trouble with the example problem we're given.

We're given this to prove:

$\sum\limits_{i=0}^{n-1}\frac{i}{2^i} = 2 - \frac{n + 1}{2^{n-1}}$

I've shown for $n = 1..3$ that the proposition holds true.

So then I go to prove the following:

$\sum\limits_{i = 0}^{n}\frac{i}{2^i} = 2 - \frac{n + 1}{2^{n - 1}} + \frac{n}{2^n} = 2 - \frac{n + 2}{2^n}$

Problem is, when I work through the algebra, I keep on ending up with $2 - \frac{3n + 2}{2^n}$.

$$\begin{eqnarray*} 2 - \frac{n + 2}{2^n} &=& 2 - \frac{n + 1}{2^{n - 1}} + \frac{n}{2^n}\\ &=& 2 - \frac{2}{2} \cdot \frac{n + 1}{2^{n - 1}} + \frac{n}{2^n}\\ &=& 2 - \frac{2n + 2}{2^n} + \frac{n}{2^n}\\ &=& 2 - \frac{2n + 2 + n}{2^n}\\ &=& 2 - \frac{3n + 2}{2^n}\\ \end{eqnarray*}$$

Am I going about this in the right way? I thought the induction step was pretty straightforward for this example, but since the algebra is not working out I'm worried I missed something earlier on.

-
Too complicated! $\frac{n+1}{2^{n-1}}=\frac{2n+2}{2^n}$. Now that you have a common denominator, you can add/subtract freely. Watch out for minus sign issues. There was one in your solution, it would have worked otherwise. The second displayed line is wrong. – André Nicolas Oct 18 '11 at 7:18
The algebraic error is you changed $\circ-\circ+\circ$ into $\circ-(\circ+\circ)$ from line 1 to 2. – anon Oct 18 '11 at 7:24
Okay... now you moved the error down to lines 3 and 4 :D – anon Oct 18 '11 at 7:49
Haha sorry, I was simplifying while you wrote your comment and answer >_<. And now after your answer & comments and staring at it I'm seeing the sign error. :) Thanks so much for bearing with me you guys, this is my first math class in 3 years. – bearcdp Oct 18 '11 at 7:57

The algebraic mistake is from the first to the second line: you reformed a $\circ-\circ+\circ$ expression invalidly into a $\circ-(\circ+\circ)$ expression, which doesn't accord with the original signs. Anyway, it looks like your local mode of attack was to take $2-(n+2)/2^n$ and aimlessly rearrange it, but I don't see that getting you anywhere. What would be easier for me is to define the function from the RHS of the original formula as $f(n)=2-(n+1)/2^{n-1}$ and show that $f(n)+n/2^n=f(n+1)$ by manipulating the left side to look like the right side, so that if the given formula holds for $n$ it must hold for $n+1$ too (do you see why that implication follows?). The base case you should check is obvious, simply observe for $n=1$ that $0/2^0=2-(1+1)/2^{1-1}=f(1)$.
Edit: Observe $$2-\frac{n+1}{2^{n-1}}+\frac{n}{2^n}=2-\frac{2(n+1)}{2^n}-\frac{-n}{2^n}=2-\frac{2(n+1)+(-n)}{2^n}.$$