Thread: Where did I go wrong on this proof? (Mathematical Induction)

I apologize in advance for not knowing how to type mathematical notation, I'll do the best I can to make the question as clear as possible.

The problem is:

Show that (sigma)(i=1 to n) i/(2^i) = 2 - (n+2) / (2^n) for all natural numbers n.

Here is what I did:

Proof. We proceed by weak mathematical induction.

Base Case. Put n = 1. Then (sigma)(i=1 to n) i/(2^i) = (sigma)(i=1 to 1) i/(2^i) = 1/(2^1) = 1/2 = 2 - (1+2)/(2^1) = 2 - (n+2)/(2^n) , so the base case is established.

Induction Step. Fix a natural number n and suppose (sigma)(i=1 to n) i/(2^i) = 2 - (n+2)/(2^n).
Observe that (sigma)(i=1 to (n+1)) i/(2^i)
= 1/(2^1) + 2/(2^2) + 3/(2^3) +...+ (n+1)/(2^(n+1))
= [1/(2^1) + 2/(2^2) + ... + n/(2^n)] + (n+1)/(2^(n+1))
= [(sigma)(i=1 to n) i/(2^i)] + (n+1)/(2^(n+1))
= [2 - (n+2)/(2^n)] + (n+1)/(2^(n+1))
= [2 - (2)(n+2) / (2)(2^n)] + (n+1)/(2^(n+1))
= [2 - (2n+4) / (2^(n+1))] + (n+1)/(2^(n+1))
= 2 - (3n+5) / (2^(n+1))
= 2 - (3n + 3 + 2) / (2^(n+1))
= 2 - [3(n+1) + 2] / (2^(n+1))

My goal was to show 2 - [(n+1)+2] / (2^(n+1)) ... I got really close except for the extra 3. Did I do something wrong, or is the proof finished?

Again, I apologize if this is difficult to read...

Originally Posted by Lprdgecko

I apologize in advance for not knowing how to type mathematical notation, I'll do the best I can to make the question as clear as possible.

The problem is:

Show that (sigma)(i=1 to n) i/(2^i) = 2 - (n+2) / (2^n) for all natural numbers n.

Here is what I did:

Proof. We proceed by weak mathematical induction.

Base Case. Put n = 1. Then (sigma)(i=1 to n) i/(2^i) = (sigma)(i=1 to 1) i/(2^i) = 1/(2^1) = 1/2 = 2 - (1+2)/(2^1) = 2 - (n+2)/(2^n) , so the base case is established.

Induction Step. Fix a natural number n and suppose (sigma)(i=1 to n) i/(2^i) = 2 - (n+2)/(2^n).
Observe that (sigma)(i=1 to (n+1)) i/(2^i)
= 1/(2^1) + 2/(2^2) + 3/(2^3) +...+ (n+1)/(2^(n+1))
= [1/(2^1) + 2/(2^2) + ... + n/(2^n)] + (n+1)/(2^(n+1))
= [(sigma)(i=1 to n) i/(2^i)] + (n+1)/(2^(n+1))
= [2 - (n+2)/(2^n)] + (n+1)/(2^(n+1))
= [2 - (2)(n+2) / (2)(2^n)] + (n+1)/(2^(n+1))
= [2 - (2n+4) / (2^(n+1))] + (n+1)/(2^(n+1))
= 2 - (3n+5) / (2^(n+1))
= 2 - (3n + 3 + 2) / (2^(n+1))
= 2 - [3(n+1) + 2] / (2^(n+1))

My goal was to show 2 - [(n+1)+2] / (2^(n+1)) ... I got really close except for the extra 3. Did I do something wrong, or is the proof finished?

Again, I apologize if this is difficult to read...

Yes...it is VERY difficult to read. Perhaps somebody else can understand it better, but in the meantime why won't you learn

how to type LaTeXin the site? Go to the help section.

You could also type it nicely on a JPG or PDF (not .DOC !) file and attach it to your question.

Tonio

Its correct until four before the bottom line:

= [2 - (2n+4) / (2^(n+1))] + (n+1)/(2^(n+1))



You just added the two terms in the numerator as they were both negative. Take the different signs into consideration and the next step will yield your solution. PS: Don't forget to show that it is true for some specific value of n to complete your induction proof.

Here it is written out, though I just saw raphw's reply. Thanks!