# Induction Proof

1. May 1, 2013

### 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}$

Last edited: May 1, 2013
2. May 1, 2013

### Staff: Mentor

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