Induction proof: sum of binomial coefficients

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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