# Prove by induction. How do I prove $\sum_{i=0}^n2^i=2^{n+1}-1$ with induction?

$\displaystyle\sum_{i=0}^n2^i=2^{n+1}-1$.

I don't understand induction so I could use some help.

-
@Paul, could you fix your edit, as you forgot the $2^i$ on the left. – Holdsworth88 Mar 24 '12 at 7:06
@Pjennings: Oh, sorry. But someone fixed it already. – Paul Mar 24 '12 at 7:15
See this answer to a similar question that did not insist on a proof via induction. – Dilip Sarwate Aug 30 '12 at 11:05
This is a very similar question, too: Prove by induction that $2^1+2^2+2^3+2^4+ \cdots +2^n=2(2^n-1)$. (And you can also check the questions linked to that one.) – Martin Sleziak Aug 30 '12 at 15:03

The base case is the calculation $2^0=2-1$. Assume $\sum_{i=0} ^{n-1} 2^i=2^n-1$ (this is the induction step). Adding $2^n$ to both sides gives:

$$\sum_{i=0} ^{n} 2^i=2^n-1+2^n=2\cdot2^n-1=2^{n+1}-1,$$

closing the induction and finishing the proof.

A combinatorial approach to the problem is as follows. The total number of subsets of a set of size $n$ is $2^{n}$. Let $N_i=\{1,2,...,i\}$. Then the total number of subsets of $N_{j-1}$ is $2^{j-1}$. Every element of each subset of $N_{j-1}$ is less than $j$, therefore affixing $j$ to each of these subsets creates an exhaustive list of the subsets of $N$ which have $j$ as their greatest element.

As before, the total number of nonempty subsets of $N=\{1,2,...,n+1\}$ is $2^{n+1}-1$, since we are taking away the empty set. Another way to count this is to count the number of subsets of $N$ with $j$ as their greatest element. We can partition $P(N)\setminus \emptyset$, where $P(X)$ denotes the power set of $X$, as follows: let $X_i$ denote the set of subsets of $N$ which have $i$ as there greatest element. Then $P(N)\setminus \emptyset=\bigcup_{i=1} ^{n+1} X_i$, which implies:

$$\sum_{i=0} ^{n} 2^i=2^{n+1}-1$$

-
right absolutely +1 – dato datuashvili Mar 24 '12 at 7:16

First let us check the base case i.e. $n=0$. $$\sum_{i=0}^02^i=2^0=1$$ $$2^{0+1}-1=1$$ Therefore the statement is true for $n=0$.

Now assume that the statement is true for $n$: $\displaystyle\sum_{i=0}^n2^i=2^{n+1}-1$. We must show that it is also true for $n+1$: $$\sum_{i=0}^{n+1}2^i=\sum_{i=0}^{n}2^i+2^{n+1}=2^{n+1}-1+2^{n+1}=2\cdot2^{n+1}-1=2^{n+2}-1 \ \Box$$

So (i) the statement is true for $n=0$; and (ii) if the statement is true for $n$, then it is also true for $n+1$. Hence, by induction, it is true for all $n \ge 0$.

-
Induction by obfuscation! This is completely garbled, I'm afraid. – TonyK Mar 24 '12 at 18:50
@TonyK the last section was intended to clarify the process of induction since the OP stated he did not get it. However I realize it may have been rather garbled and so I removed it. I hope that made it clearer. Fell free to suggest any more improvements. – E.O. Mar 24 '12 at 22:04
@E.O. I think you intend to say that we want to show it also holds for $n+1$. The way you state it implies that making the assumption means it also holds for the $(n+1)$th case. – Kurtis Zimmerman Mar 24 '12 at 23:04
@Emile: I have tried to edit your post so that it shows the structure of the proof more clearly. I hope this is OK. – TonyK Mar 24 '12 at 23:17
@TonyK Ahh.. Thanks. I did indeed mess up the wording :) – E.O. Mar 25 '12 at 0:06

The goal with mathematical induction is to prove the hypothesis true for the base case, and then show that if it holds for some arbitrary case (typically called $k$), it also holds for the next case ($k+1$).

For your problem, our base case occurs when $n = 0$.

$$\sum\limits_{i=0}^{0} 2^i = 2^0 = 1 = 2^1 - 1$$

Then, we assume that for some $k \geq 0$, the following holds:

$$\sum\limits_{i=0}^{k} 2^i = 2^{k+1} - 1$$

Now, if we can show that this being true implies that the hypothesis also holds for the $(k+1)$th case, the hypothesis must hold for all positive integers. So we have

$$\sum\limits_{i=0}^{k+1} 2^i = \sum\limits_{i=0}^{k} 2^i + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1} = 2 \cdot 2^{k+1} - 1 = 2^{(k+1) + 1} - 1.$$

Thus, the hypothesis holds for all $n \geq 0$.

-
When "we assume for all $k \geq 0$, the following holds: $\displaystyle \sum_{i=0}^k 2^i = 2^{k+1}-1$", we have already assumed what we have to prove. – Dilip Sarwate Aug 30 '12 at 11:09
Whoops, my mistake. You're right. I believe the new wording conveys the right idea. – Kurtis Zimmerman Sep 2 '12 at 17:44
No, the new wording is still not quite right. You need to say "assume that for some positive integer $k$, the following holds:" and prove the result holds for $k+1$. An alternative version (not needed in the proof in this instance) would be "assume that the following holds for all integers $k$, $0 \leq k \leq n$" and then prove the result for $k = n+1$. – Dilip Sarwate Sep 2 '12 at 21:51
Argh. I had the word "some" in there but I didn't save correctly. It should read right now. – Kurtis Zimmerman Sep 3 '12 at 1:05