# Inequality ${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 (Wayback Machine).

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?

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 E 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

I found a different proof of this fact avoiding Stirling.

Note $f(x) = (\frac{ex}{k})^k$ is a $C^2$ strictly convex function.
So $f(x) + f'(x)h < f(x+h)$ for $0 < h$

In particular, letting $h = 1$ we get

$$f'(x-1)+ f(x-1) < f(x)$$ $$(\frac{e(x-1)}{k})^{k-1}e + (\frac{e(x-1)}{k})^k< (\frac{ex}{k})^k$$ Noting that $(\frac{k}{k-1})^{k-1} < e$ since the ratio limits to $e$ from below. Substituting in the LHS for the second $e$, we get $$(\frac{e(x-1)}{k})^{k-1}(\frac{k}{k-1})^{k-1} + (\frac{e(x-1)}{k})^k< (\frac{ex}{k})^k$$ $$(\frac{e(x-1)}{k-1})^{k-1} + (\frac{e(x-1)}{k})^k< (\frac{ex}{k})^k$$

Now the result follows by induction on $n+k$ for $k\lt n$, and Pascal's formula.

$\binom {n-1}{k} + \binom {n-1}{k-1} = \binom {n}{k}$
$\binom {n-1}{k} \le (\frac{e(n-1)}{k})^k$ and $\binom {n-1}{k-1} \le (\frac{e(n-1)}{k-1})^{k-1}$ imply $\binom{n}{k} \le (\frac{en}{k})^k$

The base case $\binom{n}{n}$ and $\binom{n}{0}$ and $\binom{n}{1}$ are trivial so we can avoid the technicality where $k=1$ and $k=0$.

\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
• Thanks Brian for the clarification! – adamG Feb 23 '13 at 13:13
• @adamG: My pleasure! (Over the years I’ve been hung up often enough over such things.) – Brian M. Scott Feb 23 '13 at 13:16