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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.