Mathematical induction

1. Jan 29, 2012

foreverdream

I have an idea of what to do and I have reached the stage but when i am at final stage- I am struggling to simplify as i simply don't understand

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

so I have done p(k) and p(k+1)

this gives me p(k)
(1/2)+(2/2^2) +(3/2^3)+...+ (k/2^k) = 2 - (k+2/2^k)

Next for p(k+1)
I get
(1/2)+(2/2^2) +(3/2^3)+...+ (k+1/2^k+1)

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

now I am stuck in doing algebra.....................???????????????

2. Jan 29, 2012

vela

Staff Emeritus
Yes, it's just algebra now. You want to show that from what you have, it follows that $$\frac{1}{2} + \frac{2}{2^2} + \cdots + \frac{k+1}{2^{k+1}} = 2 - \frac{(k+1)+2}{2^{k+1}}.$$

3. Jan 30, 2012

foreverdream

Yes I know but I can't seem to materialise step showing that final out come.

4. Jan 30, 2012

vela

Staff Emeritus
Just combine the last two terms:
$$-\frac{k+2}{2^k}+\frac{k+1}{2^{k+1}} =\ ?$$

5. Jan 30, 2012

foreverdream

that simplification is what i am getting wrong

6. Jan 30, 2012

vela

Staff Emeritus

7. Jan 30, 2012

foreverdream

Ok here it is:
2- (k+1)/2^k + (k+2)/2^k+1

=2-( 2^k+1(k+1)+(k+2)2^k )/ 2^k(2^k+1)
=2- 2^k+k+1 + 2^k+k + 4^k and then denominator as above. After this it doesn't make sense

8. Jan 30, 2012

vela

Staff Emeritus
You need to use parentheses to make clear what you mean. I think you meant
$$2 - \frac{k+1}{2^k} + \frac{k+2}{2^{k+1}} = 2 - \frac{2^{k+1}(k+1) + (k+2)2^k}{2^k 2^{k+1}}$$which is correct. I'm not sure what you did next, though.
What was your thinking here? It looks like you tried to combine the factors out front with the exponents, which you can't do.

One of the rules of exponents is
$$x^a x^b = x^{a+b}$$If you have the product of some number x taken to two powers a and b, you can combine it into x taken to the sum a+b of those powers — or vice versa. Use that rule on the 2k+1 in the numerator, and then pull out the common factor from the two terms in the numerator.

Last edited: Jan 30, 2012
9. Jan 30, 2012

foreverdream

Don't worry I sorted it. Thanks for your help.