Exercise C.1.12

$\star$ Use induction on all integers $k$ such that $0 \le k \le n/2$ to prove inequality (C.6) and use equation (C.3) to extend it to all integers $k$ such that $0 \le k \le n$.

Thanks to this answer, first we rearrange the inequality:

$$ \binom{n}{k} \le \frac{n^n}{k^k(n-k)^{n-k}} \\ \Downarrow \\ \frac{k^k}{k!} \cdot \frac{(n-k)^{n-k}}{(n-k)!} \le \frac{n^n}{n!} \\ \Downarrow \\ \frac{k^k}{k!} \cdot \frac{m^m}{m!} \le \frac{(k+m)^{k+m}}{(k+m)!}$$

Where $m = n-k$. Then we need to know that $\Big(1 + \frac{1}{n}\Big)^n$ is monotonous. This is not that surprising, because:

$$\lim_{x \to +\infty}\Big(1 + \frac{1}{n}\Big)^n = e$$

Finally, we go like this:

$$ \begin{aligned} \frac{k^k}{k!} \cdot \frac{(m+1)^{m+1}}{(m+1)!} &= \frac{k^k}{k!} \cdot \frac{(m+1)^m}{m!} \\ &= \frac{k^k}{k!} \cdot \frac{m^m}{m!} \Bigg(1+\frac{1}{m}\Bigg)^m \\ &\le \frac{(k+m)^{k+m}}{(k+m)!}\Bigg(1+\frac{1}{m}\Bigg)^m & \text{(inductive hypothesis)} \\ &\le \frac{(k+m)^{k+m}}{(k+m)!}\Bigg(1+\frac{1}{k+m}\Bigg)^{k+m} & \text{(monotonicity)} \\ &= \frac{(k+m+1)^{k+m}}{(k+m)!} &= \frac{(k+m+1)^{k+m+1}}{(k+m+1)!} \end{aligned} $$