1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The problem is that you prove nothing during the induction phase. $\endgroup$ – Damien L Feb 5 '13 at 21:56
  • $\begingroup$ yeaaah, this is my problem i think. can you please give me more steps in between? $\endgroup$ – doniyor Feb 5 '13 at 21:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Clayton Feb 5 '13 at 21:58
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Brian, brilliant. my Bad, i am soo dumb. thank you so much $\endgroup$ – doniyor Feb 5 '13 at 22:05
  • $\begingroup$ @doniyor: You’re very welcome. $\endgroup$ – Brian M. Scott Feb 5 '13 at 22:05
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ wow, great. thanks Adi. there are so smooth and beautiful ways... $\endgroup$ – doniyor Feb 5 '13 at 22:24
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ i just blindly wrote $2^{n+1}-1$. i didnot know how to come to solution thru binomials. $\endgroup$ – doniyor Feb 5 '13 at 22:00

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.