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.