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.

Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$.

Today I wrote calculus exam, I had this problem given.

I have the feeling that I will get $0$ points for my solution, because I did this:

Base Case: $n=1$
$$\sum_{k=1}^{1} \binom 1 1 = 1 = 2^1 -1 .$$

Induction Hypothesis: for all $n \in \mathbb{N}$: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$

Induction Step: $n \rightarrow n+1$
$$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = 2^{n+1} -1$$

Please show me my mistake because next time is my last chance in this class.

share|improve this question
    
The problem is that you prove nothing during the induction phase. –  Damien L Feb 5 '13 at 21:56
    
yeaaah, this is my problem i think. can you please give me more steps in between? –  doniyor Feb 5 '13 at 21:57
1  
Another nitpick, your hypothesis is what you want to prove. You should say that there exists an $n\in\Bbb N$ such that for all $k\leq n$ the identity holds. –  Clayton Feb 5 '13 at 21:58

3 Answers 3

up vote 3 down vote accepted

Your first mistake is that you stated the induction hypothesis incorrectly: it should be simply that

$$\sum_{k=1}^n\binom{n}k=2^n-1\;.\tag{1}$$

What you gave as induction hypothesis is actually the theorem that you’re trying to prove!

Now, assuming $(1)$ you want to prove that $$\sum_{k=1}^{n+1}\binom{n+1}k=2^{n+1}-1\;.$$

This is an occasion when it’s not a good idea to split off the last term. Instead, use the Pascal’s triangle identity for binomial coefficients:

$$\begin{align*} \sum_{k=1}^{n+1}\binom{n+1}k&=\sum_{k=1}^{n+1}\left(\binom{n}k+\binom{n}{k-1}\right)\\\\ &=\sum_{k=1}^{n+1}\binom{n}k+\sum_{k=1}^{n+1}\binom{n}{k-1}\\\\ &\overset{*}=\sum_{k=1}^n\binom{n}k+\sum_{k=0}^n\binom{n}k\\\\ &=\left(2^n-1\right)+\binom{n}0+\sum_{k=1}^n\binom{n}k\\\\ &=2^n-1+1+2^n-1\\\\ &=2\cdot2^n-1\\\\ &=2^{n+1}-1\;. \end{align*}$$

At the starred step I used the fact that $\binom{n}{n+1}=0$ to drop the last term of the first summation, and I did an index shift, replacing $k-1$ by $k$, in the second summation.

share|improve this answer
    
Brian, brilliant. my Bad, i am soo dumb. thank you so much –  doniyor Feb 5 '13 at 22:05
    
@doniyor: You’re very welcome. –  Brian M. Scott Feb 5 '13 at 22:05

suppose that $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ then $$\sum_{k=1}^{n+1} \binom {n+1}{k} =\sum_{k=1}^{n+1}\Bigg( \binom {n}{ k} +\binom{n}{k-1}\Bigg)=$$ $$=\sum_{k=1}^{n+1} \binom {n}{ k} +\sum_{k=1}^{n+1}\binom{n}{k-1}=$$ $$=\sum_{k=1}^{n} \binom {n}{ k}+\binom{n}{n+1}+\sum_{k=0}^{n} \binom {n}{k}=$$ $$=\sum_{k=1}^{n} \binom {n}{ k}+\binom{n}{n+1}+\binom{n}{0}+\sum_{k=1}^{n} \binom {n}{k}=$$ $$=2\sum_{k=1}^{n} \binom {n}{ k}+\binom{n}{n+1}+\binom{n}{0}=$$ since $\binom{n}{n+1}=0, \binom{n}{0}=1$ $$=2\sum_{k=1}^{n} \binom {n}{ k}+1=2(2^n-1)+1=2^{n+1}-2+1=2^{n+1}-1$$

share|improve this answer
    
wow, great. thanks Adi. there are so smooth and beautiful ways... –  doniyor Feb 5 '13 at 22:24

There are a few points where I'd suspect someone could take issue with your answer:

The Induction Hypothesis is supposed to be the idea that given the hypothesis holds for a set of values from the base case up to an n that you could use that to prove the n+1 case. You seem to imply that the Induction Hypothesis holds for all natural numbers which is a bit of an overstatement to my mind.

Lastly, where is the use of the induction hypothesis in the last step? Where do you use the $2^n$-1 part that should be part of the solution.


$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = (n+1)\sum_{k=1}^{n}\binom {n} {k} + 1 = (n+1)(2^n-1)+1 = n2^n-n+2^n-1+1 = 2^n(n+1)-n$ which still has to be simplified into the final result but this at least is using the hypothesis.

share|improve this answer
    
i just blindly wrote $2^{n+1}-1$. i didnot know how to come to solution thru binomials. –  doniyor Feb 5 '13 at 22:00

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.