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".