# How to prove a formula for the sum of powers of $2$ by induction?

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. • Your induction hypothesis and what you are trying to prove for induction are both incorrect. What you are trying to prove is that the sum of the powers of $2$ up to $n$ is equal to $2^{n+1}-1$. So your inductive hypothesis should be that this result is true for $k$; that is, that $$2^0+2^1+\cdots+2^k = 2^{k+1}-1.$$What you want to prove is that from this it follows that the result is true for $k+1$, that is, that$$2^0+2^1+\cdots+2^{k}+2^{k+1} = 2^{(k+1)+1}-1\quad\mbox{holds.}$$Instead, you are trying to prove that $2^m = 2^{m+1}-1$ for all $m$, which is false. – Arturo Magidin Feb 18 '11 at 1:19

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$

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

• Thats "the simplest solution" to this problem (and the most elegant too, to me). However, OP's goal is to solve it by induction. – JnxF Jan 11 '16 at 0:25

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

I don't see the answer I like here, so I'm writing my own.

First of all, the original hypothesis is wrong: $2^0 + 2^1 + ... + 2^n = 2^{n+1}-1$

For n = 1: $2^0 + 2^1 = 2^1 - 1$ implies $3 = 1$

A correct hypothesis is: $2^1 + 2^2 + ... + 2^{n-1} = 2^n$

Basic proof:

Assume $2^1 + 2^2 + ... + 2^{n-1} = 2^n$ for all $n$. Then $2^1 + 2^2 + ... + 2^{n} = 2^{n+1}$.

$(2^1 + 2^2 + ... + 2^{n-1}) + 2^n = 2^n + 2^n = 2 \cdot 2^n = 2^{n+1}$, so we have shown $2^1 + 2^2 + ... + 2^{n} = 2^{n+1}$.