Prove Induction: (1+2+4+...+2^n)+1=2^(n+1)

[John112]

To prove: (1 + 2 + 4 + . . . + 2^{n}) + 1 = 2^{n+1} , ∀n ≥ 0 .
Basis Step n = 0: LEFT HAND SIDE: (2^{0})+ 1 = 1 + 1 = 2 RIGHT HAND SIDE 2^{0} + 1 = 2
Inductive Step: Assume (1 + 2 + 4 + . . . + 2^{k}) + 1 = 2^{k+1}
Then (1 + 2 + 4 + . . . + 2^{k} + 2^{k+1}) + 1 = 2^{k+1} + 2^{k+1} + 1 = 2^{k+2} + 1.

Is this proof right? This is a proof given to one of the example problems in the book. To me it seems wrong. If it is right then can someone explain how the +1 came to be at the end ( 2^{k+2} + 1).

Isn't the above proof should be like this?

so (1 + 2 + 4 + . . . + 2^{k} + 2^{k+1}) + 1 = 2^{k+1} + 2^{k+1} = 2^{k+2}

Because (1 + 2 + 4 + . . . + 2^{k} + 2^{k+1}) + 1 can be rewritten as

[(1 + 2 + 4 + . . . + 2^{k}) + 1] + 2^{k+1} by commutative property of addition. From the inductive step we assumed that (1 + 2 + 4 + . . . + 2^{k}) + 1 = 2^{k+1}

[(1 + 2 + 4 + . . . + 2^{k}) + 1] + 2^{k+1} = 2^{k+1} + 2^{k+1} = 2^{k+2}

 

[mfb]

Isn't the above proof should be like this?

Indeed. The second version is good, the first has some wrong "+1".