A combinatorial inequality

By exponentiation on both sides, what we basically have to prove is that $\binom nk \le (\frac {en} {k})^k$. This is true for $k = 1$ as $n \le en$ (the $k = 0$ case does not make sense because of $\log 0$). Now suppose this is true for $k$, we want to prove it is also true for $k + 1$. To do this take ratios. $$\binom n{k+1} / \binom n{k} = \frac{n-k}{k+1}\;.$$ On the other hand, $$\left(\frac {en} {k+1}\right)^{k+1} / \left(\frac {en} {k}\right)^k = \frac{n}{k+1} \times \frac{e}{(1+1/k)^k} \ge \frac{n}{k+1}$$ as $(1+1/k)^k \le e$. Also, $\frac{n}{k+1} \ge \frac{n-k}{k+1}$ obviously. So the RHS is increasing faster than the LHS at each step.


Hint :

Try to prove :

$$\binom {n}{k} \leq \frac{n^k}{k!} ~\text{ and } \frac{1}{k!} \leq \frac{e^k}{k^k}$$

using induction .