Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question
2  
@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
add comment

3 Answers 3

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

share|improve this answer
    
right absolutely +1 –  dato datuashvili Mar 24 '12 at 7:16
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
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. –  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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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