Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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

2 Answers 2

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$

share|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|improve this answer

Your Answer

 
discard

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.