26
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Feb 18 '11 at 1:19
19
$\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$
17
$\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$
  • 3
    $\begingroup$ Thats "the simplest solution" to this problem (and the most elegant too, to me). However, OP's goal is to solve it by induction. $\endgroup$ – JnxF Jan 11 '16 at 0:25
7
$\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$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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