5
$\begingroup$

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

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

  • 2
    @Paul, could you fix your edit, as you forgot the $2^i$ on the left.2012-03-24
  • 0
    @Pjennings: Oh, sorry. But someone fixed it already.2012-03-24
  • 0
    See [this answer](http://math.stackexchange.com/a/180255/15941) to a [similar question](http://math.stackexchange.com/q/180169/15941) that did not insist on a proof via induction.2012-08-30
  • 0
    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)$](http://math.stackexchange.com/questions/88132/prove-by-induction-that-21222324-cdots-2n-22n-1). (And you can also check the questions linked to that one.)2012-08-30

3 Answers 3

9

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

  • 0
    right absolutely +12012-03-24
7

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

  • 0
    Induction by obfuscation! This is completely garbled, I'm afraid.2012-03-24
  • 0
    @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.2012-03-24
  • 0
    @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.2012-03-24
  • 0
    @Emile: I have tried to edit your post so that it shows the structure of the proof more clearly. I hope this is OK.2012-03-24
  • 0
    @TonyK Ahh.. Thanks. I did indeed mess up the wording :)2012-03-25
4

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
    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.2012-08-30
  • 0
    Whoops, my mistake. You're right. I believe the new wording conveys the right idea.2012-09-02
  • 0
    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$.2012-09-02
  • 0
    Argh. I had the word "some" in there but I didn't save correctly. It should read right now.2012-09-03