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

[solomon_13000]

1 + 2 + 4 + ... + 2^n = 2^(n + 1) - 1

assume n = p
the next step n = p+1

that would mean:

[1 + 2 + 4 + ... + 2^p] + 2^(p + 1) = 2^(p + 1) - 1

[2^(p + 1) - 1] + 2^(p + 1)

2^(p + 1) - 1

Is this correct?

 

[galactus]

\(\displaystyle \L\\1+2+4+8+....+2^{n}=2^{n+1}-1\)


\(\displaystyle \L\\1+2+4+8+...+2^{n}+2^{n+1}=2^{n+1}+2^{n+1}-1=4\cdot{2^{n}}-1=2^{n+2}-1\)

 

[solomon_13000]

I did this:

2^(p + 1) - 1 + 2^(p + 1)

2^p x 2^1 - 1 + 2^p x 2^1

2^p x 2 - 1 + 2^p x 2

2^p x 2 + 2^p x 2 - 1

4 x 2^p - 1

2^(n + 2) - 1

so 2^(n + 2) - 1 is

2^n x 2^2 - 1

2^n x 4 - 1

I can understand now. Thanks.

 

[stapel]

...so 2^(n + 2) - 1 is

2^n x 2^2 - 1

2^n x 4 - 1

Unfortunately, the exercise did not ask you to prove that 2ⁿ⁺² - 1 equalled 4(2ⁿ) - 1. You were instead asked to prove a formula regarding a summation.

Try working through the steps they taught you in class for induction proofs:

i) Show that the formula works for some starting value (usually n = 1).

ii) Assume that the formula works for some unnamed value, n = k (or n = p).

iii) Show that, assuming (ii), the formula then works for n = k + 1 (or n = p + 1).

Conclude that, since (i) shows that the formula works somewhere and since (ii) and (iii) show that the formula will work for "the next" value (given some starting value), then the formula works everywhere.

In this case:

i) Show that the formula, 1 + 2 + 4 + ... + 2ⁿ = 2ⁿ⁺¹ - 1 works for n = 1.

ii) Write out your assumption step for n = k.

iii) Let n = k + 1. Plug "k + 1" into one side (probably the complicated side) of the formula. Break out the assumption-step information, and substitute what you assumed. See if you can rearrange what you've got into what you need for the other side of the formula.

I would work on the "1 + 2 + 4 + ... + 2^k + 2^k+1" side, personally.

Eliz.