5
$\begingroup$

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

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

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

  • 0
    Argh. I had the word "some" in there but I didn't save correctly. It should read right now.2012-09-03