Short and intuitive proof that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$

Solution 1:

$n^k$ is the number of ways of picking $k$ balls from $n$ balls with repetition allowed. One can generate all the possible ways by first deciding which $k$ out of $n$ balls to draw and draw from the $k$ selected balls instead. There are $\binom{n}{k}$ ways to choose the $k$ balls and $k^k$ ways to pick from the selected $k$ balls with repetition allowed. This gives us $$n^k \le\binom{n}{k} k^k \quad\iff\quad \left(\frac{n}{k}\right)^k \le \binom{n}{k}$$

Solution 2:

Note first that for all $0 \leq i < k \leq n$ we have $k(n-i) = kn - ki > kn - ni =\geq n(k-i)$, and hence $\frac{n-i}{k-i} \geq \frac{n}{k}$. Therefore $${n \choose k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots 1} = \prod_{i=0}^{k-1} \frac{n-i}{k-i} \geq \prod_{i=0}^{k-1} \frac{n}{k} = \left(\frac{n}{k}\right)^k.$$

Solution 3:

For every $1\leqslant k\leqslant n$ and $0\leqslant i\leqslant k-1$, $$ k\leqslant n\implies\frac{i}k\geqslant\frac{i}n\implies 1-\frac{i}k\leqslant1-\frac{i}n. $$ Each term is positive, hence the products are in the same order, that is, $$ \frac{k!}{k^k}=\prod_{i=0}^{k-1}\left(1-\frac{i}k\right)\leqslant\prod_{i=0}^{k-1}\left(1-\frac{i}n\right)=\frac{n!}{n^k(n-k)!}. $$ Multiply the leftmost and rightmost terms by $\dfrac{n^k}{k!}$... Et voilà!