# inductive prove$\sum_{k=1}^{n} \binom n k = 2^n -1$

today i wrote calculus exam, i had this problem given, which was to prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1$$ for all $n\in \mathbb{N}$

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

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

## 3 Answers

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.

-

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

## Did you find this question interesting? Try our newsletter

email address

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

-

wow, great. thanks Adi. there are so smooth and beautiful ways... – doniyor Feb 5 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.

-

i just blindly wrote $2^{n+1}-1$. i didnot know how to come to solution thru binomials. – doniyor Feb 5 at 22:00
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 14, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9574621319770813, "perplexity_flag": "head"}