How do I prove this by induction?
Prove that for every natural number n, $ 2^0 + 2^1 + ... + 2^n = 2^{n+1}-1$
Here is my attempt.
Base Case: let $ n = 0$ Then, $2^{0+1} - 1 = 1$ Which is true.
Inductive Step to prove is: $ 2^{n+1} = 2^{n+2} - 1$
Our hypothesis is: $2^n = 2^{n+1} -1$
Here is where I'm getting off track. Lets look at the right side of the last equation: $2^{n+1} -1$ I can rewrite this as the following.
$2^1(2^n) - 1$ But, from our hypothesis $2^n = 2^{n+1} - 1$ Thus:
$2^1(2^{n+1} -1) -1$ This is where I get lost. Because when I distribute through I get this.
$2^{n+2} -2 -1$ This is wrong is it not? Am I not applying the rules of exponents correctly here? I have the solution so I know what I'm doing is wrong. Here is the correct proof.
5 Answers
$\begingroup$An easy way to do this is using binary. Here's an idea of what I mean:
- $2^0$ in binary is $1$
- $2^1$ in binary is $10$
- $2^2$ in binary is $100$
For a general rule:
$2^n$ in binary is $100\cdots0$ (n zeros)
Add those together and you get $2^0 + 2^1 + ... + 2^n$ in binary is $11...11$ ($n+1$ ones).
Now it's obvious that adding 1 to that gives you $$100\cdots00 \quad\text {($n+1$ zeros)}$$ Which as we all know is $2^{n+1}$.
Thus $2^{n+1} - 1$ is equal so the sum of powers of two up to $2^n$.
$\endgroup$ 1 $\begingroup$Both
- Inductive Step to prove is: $ 2^{n+1} = 2^{n+2} - 1$
- Our hypothesis is: $2^n = 2^{n+1} -1$
are wrong and should be
- Inductive Step to prove is: $ 2^0 + 2^1 + ... + 2^n + 2^{n+1} = 2^{n+2} - 1$
- Our hypothesis is: $ 2^0 + 2^1 + ... + 2^n = 2^{n+1}-1$
Add $2^{n+1}$ to both sides of the hypothesis and you have the step to prove since $2^{n+1}-1 +2^{n+1} = 2^{n+2} - 1$
$\endgroup$ $\begingroup$HINT $\ $ Here's the inductive proof for summing a general geometric series.
THEOREM $\rm\quad 1 + x + \cdots + x^{n-1}\ =\ \dfrac{x^{n}-1}{x-1}$
Proof $\ $ Base case: It is true for $\rm\ n = 1\:,\:$ viz. $\rm\ 1 = (x-1)/(x-1)\:$.
Inductive step: Suppose it is true for $\rm\ n = k\:.\ $ Then we have
$$\rm\ x^k + (x^{k-1} +\: \cdots\: + 1)\:\ =\:\ x^k +\frac{x^k-1}{x-1}\ =\ \frac{x^{k+1}-1}{x-1}$$
which implies it is true for $\rm\: n = k+1\:,\:$ thus completing the inductive proof.
The proof you seek is just the special case $\rm\ x = 2\ $.
$\endgroup$ $\begingroup$I don't see the answer I like here, so I'm writing my own.
Basic proof:
We wish to prove $2^0 + 2^1 + ... + 2^{n-1} = 2^n - 1$ for all $n$. We can verify by inspection this is true for n=1. Next, assume that $2^0 + 2^1 + ... + 2^{n} = 2^{n+1} - 1$.
$(2^0 + 2^1 + ... + 2^n) + 2^{n+1} = (2^{n+1} - 1) + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1$, so we have shown $2^0 + 2^1 + ... + 2^{n-1} = 2^{n} - 1$ is true for all n.
$\endgroup$ 2 $\begingroup$let $S = 2^0 + 2^1 + 2^2 + .... + 2^{n-1}$
so $2S = 2^1 + 2^2 + 2^3 + 2^n$
then $2S - S = S = (2^1 - 2^0) + (2^2 - 2^1) + ... + (2^{n-1} - 2^{n-1}) + 2^n = 2^n - 1$
and we got $2^0 + 2^1 + 2^2 + .... + 2^{n-1} = 2^n - 1$
$\endgroup$
