Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. enter image description here

share|cite|improve this question
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


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

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer
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 at 0:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.