Mathematical Induction?

Question

Prove by induction that
n
Σ r/(2^r) = 2 - (1/2)^n (2+n)
r=1

Answer 1

You already stated the proposition, so now verify the base case where n=1:

1/2**1 = 2 - 1/2**1 * (2+1)
1/2 = 2 - 1/2 * 3
1/2 = 2 - 3/2
1/2 = 1/2

so we are good for the base case (I'm using old Fortran ** for the caret)

now formulate the inductive hypothesis:

the first part is the statement, just re-stated with n=m
assume the hypothesis is true for 1 <= r <= m

m/(2**m) = 2 - (.5**m)(2+m)

now show this is true for (m+1)
(m+1)/(2**(m+1))

recheck the base case for m=1

(1+1)/(2**(1+1)
2/4
1/2

This works out to our original base case, which also came out to 1/2.

Look at http://www.cc.gatech.edu/people/home/idris/AlgorithmsProject/ProofMethods/Induction/ProofByInduction.html
for the rest of this. You have to use
n+1
Σ r/(2^r) = 2 - (1/2)^n (2+n)
r=1

Then use a property of summations to get:

n
Σ r/(2^r) = 2 - (1/2)^n (2+n) + 2 - 1/2**(n+1) * (2+n+1)
r=1

and then use the inductive hypothesis. I'm getting sleepy and can't do much more of this.