Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
A related question: math.stackexchange.com/q/132519/7266 –  Fabian Apr 16 '12 at 18:51

3 Answers 3

up vote 6 down vote accepted

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$

share|improve this answer
    
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
1  
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*}$$

share|improve this answer
    
Isn't $({n/e \over (n-k)/e})^{n-k} \gt 1$ ? –  adamG Feb 23 '13 at 12:15
1  
@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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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