# Proving by induction that $\sum_{k=0}^n{n \choose k} = 2^n$

Prove by induction that for all $n \ge 0$:

$${n \choose 0} + {n \choose 1} + ... + {n \choose n} = 2^n.$$

In the inductive step, use Pascal’s identity, which is:

$${n+1 \choose k} = {n \choose k-1} + {n \choose k}.$$

I can only prove it using the binomial theorem, not induction.

For basic step n=0:
$\binom{0}{0}=\frac{0!}{0!0!}=2^0$

For induction step:
Let k be an integer such that $0\lt{k}$ and for all L, $0\le{L}\le{k}$ where $L\in{I}$, the formula stand true.
Then:
$$\binom{k}{0}+\binom{k}{1}+...+\binom{k}{k}=2^k$$
Now as can be illustrated easily $\binom{k}{0}=\binom{k+1}{0}$ and $\binom{k}{k}=\binom{k+1}{k+1}$.
Now by using Pascal's identity,
\begin{align}\binom{k+1}{0}+\binom{k+1}{1}+\binom{k+1}{2}+...+\binom{k+1}{k}+\binom{k+1}{k+1}\\=\binom{k+1}{0}+\binom{k}{0}+\binom{k}{1}+\binom{k}{1}+\binom{k}{2}+...+\binom{k}{k-1}+\binom{k}{k}+\binom{k+1}{k+1}\\=\binom{k}{0}+\binom{k}{0}+\binom{k}{1}+\binom{k}{1}+\binom{k}{2}+...+\binom{k}{k-1}+\binom{k}{k}+\binom{k}{k}\\=2*{\sum_{i=0}^k\binom{k}{i}}\\=2*2^k\\=2^{k+1}\end{align} As the formula is also true for $k+1$ hence by second principle of finite induction this formula is valid for all integers greator than or equal to $0$.

Well, here it is : $$\sum_{k=0}^{n+1} {n+1\choose k} = {n+1\choose 0 } + {n+1\choose 1 } + \ldots + {n+1\choose n } + {n+1\choose n+1}$$ $$= 1 + {n\choose 0} + {n\choose 1} + {n\choose 1} + {n\choose 2 } + \ldots + {n\choose n-1} + {n\choose n} + 1$$ $$= {n\choose 0 } + {n\choose 0 } + {n\choose 1} + {n\choose 1 } + \ldots + {n\choose n-1} + {n\choose n-1} + {n\choose n} + {n\choose n}$$ $$= 2 \times \sum_{k=0}^n {n\choose k }$$ Now induct!

• I'm not too sure what to do next – xyz Oct 9 '13 at 6:05
• Sorry nevermind, it's simple ty – xyz Oct 9 '13 at 6:18
• @PrahladVaidyanathan what is the step ${n+1 \choose 1} = {n \choose 1} + {n \choose 1}$ – bodokaiser Mar 15 '15 at 9:59