Prove 2^0+ +2^n=2^{n+1}-1

1. Jul 6, 2014

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

??

2. Jul 6, 2014

Fredrik

Staff Emeritus
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.

Last edited: Jul 6, 2014
3. Jul 12, 2014

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.

4. Jul 12, 2014

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.

5. Jul 12, 2014

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.