3
$\begingroup$

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.

  • 0
    Haha sorry, I was sim$p$lifying 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.2011-10-18

1 Answers 1

5

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}.$