5
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ Everything is right except that your inequalities are all pointing backwards. Other than that, good answer! $\endgroup$ – David E Speyer Apr 16 '12 at 18:54
  • $\begingroup$ thanks, just noticed that. $\endgroup$ – Wonder Apr 16 '12 at 18:54
  • 7
    $\begingroup$ 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!}$$ $\endgroup$ – Joel Cohen Apr 16 '12 at 21:11
  • 1
    $\begingroup$ Great, that is very nice. Thanks for pointing it out. $\endgroup$ – Wonder Apr 17 '12 at 2:40
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

$$\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*}$$

$\endgroup$
  • $\begingroup$ Isn't $({n/e \over (n-k)/e})^{n-k} \gt 1$ ? $\endgroup$ – adamG Feb 23 '13 at 12:15
  • 1
    $\begingroup$ @adamG: It’s $\left(1+\frac{k}{n-k}\right)^{n-k}\le e^k$. $\endgroup$ – Brian M. Scott Feb 23 '13 at 12:22
  • $\begingroup$ Thanks Brian for the clarification! $\endgroup$ – adamG Feb 23 '13 at 13:13
  • $\begingroup$ @adamG: My pleasure! (Over the years I’ve been hung up often enough over such things.) $\endgroup$ – Brian M. Scott Feb 23 '13 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.