Show that ${n\choose k}\leq 2^n$

Question

Show that ${n\choose k}\leq 2^n$ for all naturals with $0\leq k \leq n $.I know I need to use induction and for the base case $n=1$ what exactly am I showing?

Answer 1

Since $$ 2^n=(1+1)^n=\sum_{k=0}^n{n\choose k}, $$ it follows that $$ {n\choose k} \le 2^n\quad \forall k=0,1,\ldots,n. $$

Answer 2

Think about what the two terms mean. ${n \choose k}$ is the number of ways that you can choose $k$ elements out of a pack of $n$; $2^n$ is the size of the power set of $\{1,...,n\}$, in particular the number of ways that you can choose $r$ out of $n$, for any $r$. Thus clearly the first is a subset of the second, so the number of ways is less than or equal to.

Hope this helps give some motivation for why this is true! :)

Answer 3

For $n=0$, $\binom 00 \le 2^0$.

Assume $\binom nk \le 2^n$ for an $n\ge 0$ and for all $0\le k\le n$.

Consider $\binom {n+1}k$. If $k=0$ or $k = n+1$, then $\binom{n+1}k = 1 < 2^{n+1}$.

Otherwise, $\binom{n+1}k = \binom n{k-1} + \binom nk \le 2^n + 2^n = 2^{n+1}$.