# Stirling's Approximation for binomial coefficient

In this proof, it is assumed that, for $$k \ll n$$, $${n \choose k} \approx \frac{n^k}{k!}$$, given Stirling's approximation.

How does Stirling's Approximation, in either form $$\ln n! \approx n\ln{n} -n + (\ln(n))$$ or $$n! \approx \sqrt{2\pi n} (\frac{n}{e})^n$$, give this result?

• Stirling's approximation isn't needed here. You just need to show that $\frac{n!}{(n-k)!}\approx n^k$. Sep 23 '15 at 0:19
• Ok, but for $k <<n$ I get $\frac{n!}{(n-k)!} \approx \frac{n!}{n!} = 1$ which is where I have been stuck.
– user157818
Sep 23 '15 at 0:20
• Oh I see so can we say $\frac{n!}{(n-k)!} = \frac{n(n-1)(n-2) ... (n-k)(n-k-1) ... (1)}{(n-k)(n-k-1)...(1)}=n(n-1)(n-2)...(n-k+1)=n^k + O(n^{k -1})$
– user157818
Sep 23 '15 at 0:23
• For fixed $k\ge 1$, $\lim_{n\to\infty} \frac{n!}{(n-k)!}=\infty$, so the $\approx 1$ a few comments above is very wrong. Sep 23 '15 at 0:26

Although certainly not the most efficient approach, we can use Stirling's Formula to arrive at the asymptotic expression for $$\binom{n}{k}$$. We have

$$\frac{\sqrt{2\pi n}(n/e)^n}{k!\sqrt{2\pi(n-k)}((n-k)/e)^{n-k}}=(1-k/n)^{k-1/2}\frac{e^{-k}}{k!(1-k/n)^{n}}n^k \tag 1$$

Note that the first term on the right-hand side of $$(1)$$ tends to $$1$$ as $$n\to \infty$$. Note also that the denominator of the middle term on the right-hand side goes to $$k!e^{-k}$$. Therefore the middle term also tends to $$1/k!$$. We are left with $$n^k/k!$$ as expected.

Note that the notation $$k\ll n$$ is nebulous (See THIS note's discussion on asymptotics of the binomial coefficient). Herein, we have tacitly assumed that $$k$$ is fixed and that $$k=o(\sqrt n)$$.

• Isn't the denominator in the LHS supposed to be $\sqrt{2\pi(n-k)}$ instead of $\sqrt{\pi(n-k)}$. Feb 6 '17 at 19:01
• @Taylor Yes. I've edited. Thank you for caching the typo. Feb 6 '17 at 19:45
• I know this is quite old, but whey do you say that the first term in $(1)$ tends to $1$? The question is for $k \ll n$. But $k = n / \log n$ satisfies this. So the term actually tends to $\exp(-k^2/n)$, which may well diverge. Apr 15 '20 at 8:54
• @SamT The notation $k<<n$ is nebulous. Herein, we assumed that $k$ is fixed and that $k=o(\sqrt n)$. I added a note at the end of the post to state this assumption. Apr 15 '20 at 17:39
• @SamT You raised a good point. See this short note on the binomial coefficient. In particular, the sections on Bounds and Asymptotics are of interest here. Apr 16 '20 at 16:13

The approximation $n! \approx (n/e)^n$ suffices. As $n \to \infty$ and $k/n \to 0$ we have

$$(n-k)! \approx \left(\frac{n-k}{e}\right)^{n-k}= \left(\frac{n}{e}\right)^{n-k} (1-k/n)^{n-k} \approx\left(\frac{n}{e}\right)^{n-k} e^{-k}$$

Hence

$${n \choose k} \approx \frac{ \left(\frac{n}{e}\right)^{n}} {\left(\frac{n}{e}\right)^{n-k} e^{-k} \, k!} = \frac{n^k}{k!}$$

• This is nice but $n! \approx \frac{n^n}{e^n}$ is wrong, unless I am not interpreting $\approx$ correctly. To me, $a_n\approx b_n$ means $\frac{a_n}{b_n}\to 1$. By Stirling's theorem your approximation is off by a factor of $\sqrt{n}$, (which later cancels in the fraction expressing the binomial coefficients). Sep 30 '15 at 18:21
• I may be wrong but that double twidle sign stands for "approximately equal to". I believe you are referring to only one twidle sign when it comes to asymptotc equivalence. Jun 4 '19 at 13:59
• @Juan123 Good point, I'm being a little sloppy in that regard. Actually the first "approximation" is just that, it's not an asympotic equivalence (we'd need the factor $\sqrt{2 \pi n}$ for that). (This also answers the previous comment). Jun 4 '19 at 14:42
• I know this is old, but as with the other answer, this one also seems to be very slightly wrong. Of course, "$\approx$" can mean basically whatever you like. If "$a_n \approx b_n$" means that "$\log a_n / \log b_n \to 1$", then it's true. But you're missing a factor $\exp(-k^2/n)$, coming from $(1 - k/n)^k$. (Note that you only assume that $k/n \to 0$, not that $k^2/n \to 0$.) Apr 15 '20 at 8:56
• @SamT I wrote the first order (logarithmical) term for the approximation. Even if $k^2/n$ diverges, this is still correct, just like the usual $n! \approx (n/e)^n$ Apr 15 '20 at 11:12