# Induction proof: sum of binomial coefficients

Prove by mathematical induction for all natural numbers $n$:

$$\sum_{k=0}^{n} \binom{n}{k}=2^n$$

thus is it sufficient to show that (but I think I made a mistake) thus how to do it properly?

$$2^n+\binom{n+1}{n+1}=2^{n+1}$$

• The problem is that the first part of your sum does not add up to $2^n$. – user10444 Feb 15 '15 at 19:23
• how come? the first part is copied directly from the question – kurkowski Feb 15 '15 at 19:25
• See the answer below – user10444 Feb 15 '15 at 19:26
• The assertion that $2^n + \binom{n + 1}{n + 1} = 2^{n + 1}$ is incorrect: $2^n + \binom{n + 1}{n + 1} = 2^n + 1$. – N. F. Taussig Feb 15 '15 at 19:28

## 4 Answers

Not quite, because ${n+1\choose n+1}=1$. Combinatorically, is it easy to see that ${n+1\choose k}={n\choose k}+{n\choose k-1}$ (we either include the last element or we don't). From here on the proof is easy because (using the induction hypothesis):

$\sum_{k=0}^{n+1} {n+1\choose k}=\sum_{k=0}^{n+1} {n\choose k}+{n\choose k-1}=\sum_{k=0}^{n+1} {n\choose k}+\sum_{k=0}^{n+1} {n\choose k-1}=2^n+2^n=2^{n+1}$

Because ${n\choose -1}={n\choose n+1}=0$ (it's impossible to choose -1 or n+1 elements out of n).

Note that $$\sum_{k=0}^{n+1} \begin{pmatrix} n+1 \\ k\end{pmatrix} = \begin{pmatrix} n+1 \\ n+1\end{pmatrix} + \underbrace{\sum_{k=0}^n \begin{pmatrix} n+1 \\ k\end{pmatrix}}_{\neq 2^n}.$$

Alternatively, note that $\begin{pmatrix} n+1 \\ n+1\end{pmatrix} = 1$, and that $2^{n+1} \neq 2^n + 1$.

• thus how to approach the inductional proof? – kurkowski Feb 15 '15 at 19:26

See the answer of Arkamis to find your mistake.

Under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,\dots,n\right\}$ we have:

$$\sum_{k\in\mathbb{Z}}\binom{n+1}{k}=\sum_{k\in\mathbb{Z}}\left[\binom{n}{k-1}+\binom{n}{k}\right]=\sum_{k\in\mathbb{Z}}\binom{n}{k-1}+\sum_{k\in\mathbb{Z}}\binom{n}{k}=2^{n}+2^{n}=2^{n+1}$$

Not quite because you are missing the $n+1$ in all the sum. Anyway $2^n+1\neq 2^{n+1}$. The key is to use $\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}$.