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


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

  • $\begingroup$ right absolutely +1 $\endgroup$ 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$.

  • $\begingroup$ Induction by obfuscation! This is completely garbled, I'm afraid. $\endgroup$
    – TonyK
    Mar 24 '12 at 18:50
  • $\begingroup$ @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. $\endgroup$
    – E.O.
    Mar 24 '12 at 22:04
  • $\begingroup$ @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. $\endgroup$ Mar 24 '12 at 23:04
  • $\begingroup$ @Emile: I have tried to edit your post so that it shows the structure of the proof more clearly. I hope this is OK. $\endgroup$
    – TonyK
    Mar 24 '12 at 23:17
  • $\begingroup$ @TonyK Ahh.. Thanks. I did indeed mess up the wording :) $\endgroup$
    – 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$.

  • 2
    $\begingroup$ 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. $\endgroup$ Aug 30 '12 at 11:09
  • $\begingroup$ Whoops, my mistake. You're right. I believe the new wording conveys the right idea. $\endgroup$ Sep 2 '12 at 17:44
  • $\begingroup$ 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$. $\endgroup$ Sep 2 '12 at 21:51
  • $\begingroup$ Argh. I had the word "some" in there but I didn't save correctly. It should read right now. $\endgroup$ Sep 3 '12 at 1:05

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.