# Thread: Need help with math induction, I think I'm on right track

1. ## Need help with math induction, I think I'm on right track

2. a) Show by mathematical induction that

1/2 + 2/2^2 + 3/2^3 + ... + n/2^n = 2 - n+2/2^n

My work:

1. Show p(1) true. I did this part.

2. Assume p(k) true => assume p(k+1) true

I'm a bit stuck here. Here's how I set it up

(2 - k+2 / 2^k) + (k+1 / 2^k+1) = (2 - k+2 / 2^k) + (k+1 / 2^k+1)

I think all I have to do is simplify the right side so that it equals 2 - k+3 / 2^k+1. Please help.

2. Originally Posted by thekrown
2. a) Show by mathematical induction that

1/2 + 2/2^2 + 3/2^3 + ... + n/2^n = 2 - n+2/2^n
Does the right-hand side above mean the following?

$\displaystyle 2\, -\, \frac{n\, +\, 2}{2^n}$

Thank you!

3. Yes that is correct. I'm not really sure how to simplify the right to achieve the desired result. The exponents are bugging me.

4. To do an induction proof, you assume the n = k step, and then try to show the n = k + 1 step. You don't assume the conclusion; you have to prove it.

I'm not sure what you're doing with the n = k + 1 step...?

Since the previous (assumption) step was for n = k, you have assumed the following:

$\displaystyle \frac{1}{2^1}\, +\, \frac{2}{2^2}\, +\, \frac{3}{2^3}\, +\, ...\, +\, \frac{k}{2^k}\, =\, 2\, - \frac{k\, +\, 2}{2^k}$

You are now needing to work with:

$\displaystyle \frac{1}{2^1}\, +\, \frac{2}{2^2}\, +\, \frac{3}{2^3}\, +\, ...\, +\, \frac{k}{2^k}\, +\, \frac{k\, +\, 1}{2^{k+1}}$

...and you hope to manipulate the above to be in the form:

$\displaystyle 2\, -\, \frac{k\, +\, 3}{2^{k+1}}$

The first proof step is (usually) to substitute from the assumption step. In this case, we get:

$\displaystyle \left(2\, - \frac{k\, +\, 2}{2^k}\right)\, +\, \frac{k\, +\, 1}{2^{k+1}}$

A good first step might be to convert the second term to a common denominator with the third term, noting that $\displaystyle 2^{k+1}\, =\, 2\times 2^k$.