How to Use Induction to Prove 2^n+1 = 2^(n+1)-1?

[jonroberts74]

$$2^0+2^1+2^2+...+2^n=2^{n+1}-1;n \ge 0$$

$$P(0)$$ $$2^0=2^{0+1}-1 \rightarrow 1=1$$

$$P(k) = 2^{k+1}-1$$


$$1+2+2^2+2^k+2^{k+1}=2^{k+1}-1+2^{k+1}$$

$$2^{k+2}-1 = 2^{k+1}-1+2^{k+1}$$

$$= 2^{k+1}(1+1)-1$$

$$= 2^{k+1}(2)-1$$

$$= 2^{k+1+1}-1$$

$$= 2^{k+2}-1$$

??

 

[Fredrik]

Your solution is fine, but your presentation is hard to follow. As you know, you need to prove that $2^0=2^1-1$ and then that if $1+\cdots+2^{k}=2^{k+1}-1$ then $2^0+\cdots+2^{k+1}=2^{k+2}-1$. To prove the former, I would just write $2^0=1=2^1-1$. The calculation that proves the latter is much easier to follow in this form:
$$2^0+\cdots+2^{k+1}=(2^0+\cdots+2^k)+2^{k+1} =(2^{k+1}-1)+2^{k+1} =2\cdot 2^{k+1}-1=2^{k+2}-1.$$ Next time use the template. The moderators may delete your post if you don't.

 

[kduna]

You can also prove this without induction.

Proposition: $x^n - 1 = (x - 1)(1 + x + ... + x^{n-1})$.

The above is easily shown by distributing the entire $(1 + x + ... + x^{n-1})$ on the right hand side to yield: $(x + x^2 + ... + x^n) - (1 + x + ... + x^{n-1})$.

Now if you plug in 2 for x, you get what you were looking to prove.

 

[LCKurtz]

Or, alternatively$$
s = 2^0+2^1+...+2^n$$ $$
2s=2^1+2^2+...+2^n+2^{n+1}$$Subtract the first from the second:$$
s=-2^0+2^{n+1} =2^{n+1}-1$$It's just the old geometric series trick.

 

[thelema418]

I think what you are struggling with is a way of thinking about the algebra logic.

You assume P(k) in the induction. (Make certain to state this as an assumption.) You want to show P(k+1) holds by starting with the left-hand side and using the P(k) assumption. I'm writing ? to indicate that I stop and think, what type of relation can I make from the known information.

$2^0 + 2^1 + \cdots + 2^k + 2^{k+1} = ?$ Given LHS.
$= (2^0 + 2^1 + \cdots + 2^k) + 2^{k+1} = ?$ Recognize P(k)
$= (2^{k+1} -1) + 2^{k+1} = ?$ Substitute P(k).
$=2(2^{k+1}) -1 = ?$ Regrouping.
$=2^{(k+1)+1} - 1$ Determined RHS.

Your solution has a lot of extraneous information, so I think you are trying to "balance" an equation. You really just have to set up a series of relations.