${n \choose k} \leq \left(\frac{en}{ k}\right)^k$

Question

This is from page 3 of http://www.math.ucsd.edu/~phorn/math261/9_26_notes.pdf.

Copying the relevant segment:

Stirling’s approximation tells us $\sqrt{2\pi n} (n/e)^n \leq n! \leq e^{1/12n} \sqrt{2\pi n} (n/e)^n$. In particular we can use this to say that $$ {n \choose k} \leq \left(\frac{en}{ k}\right)^k$$

I tried the tactic of combining bounds from $n!$, $k!$ and $(n-k)!$ and it didn't work. How does this bound follow from stirling's approximation?

Answer 1

First of all, note that $n!/(n-k)! \le n^k$. Use Stirling only for $k!$.

${n \choose k} \le \frac{n^k}{k!} \le \frac{n^k}{(\sqrt{2\pi k}(k/e)^k)} \le \frac{n^k}{(k/e)^k} = (\frac{en}{k})^k$

Answer 2

$$\begin{align*} \binom{n}k&=\frac{n!}{k!(n-k)!}\\ &\le\frac{e^{1/12n} \sqrt{2\pi n} (n/e)^n}{\sqrt{2\pi k}(k/e)^k\sqrt{2\pi(n-k)}((n-k)/e)^{n-k}}\\ &=\frac{e^{1/12n}\sqrt{n}}{\sqrt{2\pi k(n-k)}}\left(\frac{n/e}{k/e}\right)^k\left(\frac{n/e}{(n-k)/e}\right)^{n-k}\\ &\le\frac{e^{1/12n}\sqrt{n}}{\sqrt{2\pi k(n-k)}}\left(\frac{n}{k/e}\right)^k\\ &\le\frac{e^{1/12n}\sqrt{n}}{\sqrt{2\pi(n-1)}}\left(\frac{en}k\right)^k\\ &\le\left(\frac{en}k\right)^k \end{align*}$$