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.

Solution 1:

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

Solution 2:

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!