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

Question

I have proved previously that $\sum_{k=0}^n {n \choose k} = 2^n$ by using the binomial theorem. I was wondering, however if it were possible to solve this using a proof of induction.

Answer 1

By induction

For $n=0$ it's obvious. $$\sum_{k=0}^{n+1}\binom{n+1}{k}=2+\sum_{k=1}^n\binom{n+1}{k}.$$ You have that $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$ and thus $$\sum_{k=1}^n\binom{n+1}{k}=\underbrace{\sum_{k=1}^n\binom{n}{k}}_{=2^n-1}+\sum_{k=1}^n\binom{n}{k-1}=2^n-1+\underbrace{\sum_{k=0}^{n-1}\binom{n}{k}}_{=2^n-1}=2^n-1+2^n-1=2^{n+1}-2.$$

Therefore, we get $$\sum_{k=0}^{n+1}\binom{n+1}{k}=2^{n+1}-2+2=2^{n+1}.$$