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

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?

-
A related question: math.stackexchange.com/q/132519/7266 –  Fabian Apr 16 '12 at 18:51

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$

-
Everything is right except that your inequalities are all pointing backwards. Other than that, good answer! –  David Speyer Apr 16 '12 at 18:54
thanks, just noticed that. –  Wonder Apr 16 '12 at 18:54
This might be useless, but the inequality you're using (namely $k! \ge k^k e^{-k}$) has a very elementary proof (without need for the full Stirling) : $$e^k = \sum_{i = 0}^{\infty} \frac{k^i}{i!} \ge \frac{k^k}{k!}$$ –  Joel Cohen Apr 16 '12 at 21:11
Great, that is very nice. Thanks for pointing it out. –  Wonder Apr 17 '12 at 2:40
\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*}
Isn't $({n/e \over (n-k)/e})^{n-k} \gt 1$ ? –  adamG Feb 23 '13 at 12:15
@adamG: It’s $\left(1+\frac{k}{n-k}\right)^{n-k}\le e^k$. –  Brian M. Scott Feb 23 '13 at 12:22