Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.