Here's a (possibly sloppily written) Induction proof that has me stumped. It's the first example from here and supposedly the statement holds?
(*) For n > 1, 2 + 2^2 + 2^3 + 2^4 + ... + 2^n = 2^n+1 – 2
Let n = 1. Then:
2 + 2^2 + 2^3 + 2^4 + ... + 2^n = 2^1 = 2
...and:
2^n+1 – 2 = 2^1+1 – 2 = 2^2 – 2 = 4 – 2 = 2
So (*) works for n = 1.
Assume, for n = k, that (*) holds; that is, that
2 + 2^2 + 2^3 + 2^4 + ... + 2^k = 2^k+1 – 2
Let n = k + 1.
I understand this part. This is where I get lost. (I understand that first we set n=k and then n=k+1 but the equations are sloppy and I don't follow how both sides are "equal" as the original statement asks me to prove.
2 + 2^2 + 2^3 + 2^4 + ... + 2^k + 2^k+1 | (I assume this is the left side)
= [2 + 2^2 + 2^3 + 2^4 + ... + 2^k] + 2^k+1| (still on the left side)
= [2^k+1 – 2] + 2^k+1 | (now we are on the right side??)
= 2×2^k+1 – 2 | (right side simplified)
= 2^1×2^k+1 – 2
= 2^k+1+1 – 2
= 2^(k+1)+1 – 2
Then (*) works for n = k + 1.
Ok, so what is the final conclusion? Looks to me the sides are not equal but it's not evident what the final answer is. Seems like the statement "Then (*) works for n = k + 1." suggests that the statement holds true but I fail to see why. Thanks!
The goal of the induction step is to show that (*) holds for $n = k+1$, in particular, we want to show $$2 + 2^2 + \cdots + 2^{k+1} = 2^{(k+1)+1}-2$$ The induction hypothesis says $2 + 2^2 + \cdots + 2^{k} = 2^{k+1}-2$. So we start with the LHS of what we want to show, and transform it to the RHS, using things we know are true. In particular
$2 + 2^2 + \cdots + 2^{k+1} = (2 + 2^2 + \cdots 2^k)+ 2^{k+1}$
$= (2^{k+1}-2) + 2^{k+1}$ by the induction hypothesis.
$= 2 \cdot 2^{k+1} - 2$ re-arranging
$= 2^{(k+1)+1} - 2$ (re-arranging some more)
And so, we have showed the LHS of what we wanted equals the RHS of what we wanted, which completes the induction.