15
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Stirling's approximation isn't needed here. You just need to show that $\frac{n!}{(n-k)!}\approx n^k$. $\endgroup$
    – Joey Zou
    Sep 23 '15 at 0:19
  • 1
    $\begingroup$ Ok, but for $k <<n$ I get $\frac{n!}{(n-k)!} \approx \frac{n!}{n!} = 1$ which is where I have been stuck. $\endgroup$
    – user157818
    Sep 23 '15 at 0:20
  • $\begingroup$ 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})$ $\endgroup$
    – user157818
    Sep 23 '15 at 0:23
  • 3
    $\begingroup$ 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. $\endgroup$ Sep 23 '15 at 0:26
9
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Isn't the denominator in the LHS supposed to be $\sqrt{2\pi(n-k)}$ instead of $\sqrt{\pi(n-k)}$. $\endgroup$
    – Taylor
    Feb 6 '17 at 19:01
  • $\begingroup$ @Taylor Yes. I've edited. Thank you for caching the typo. $\endgroup$
    – Mark Viola
    Feb 6 '17 at 19:45
  • $\begingroup$ 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. $\endgroup$
    – Sam OT
    Apr 15 '20 at 8:54
  • $\begingroup$ @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. $\endgroup$
    – Mark Viola
    Apr 15 '20 at 17:39
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mark Viola
    Apr 16 '20 at 16:13
6
$\begingroup$

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!} $$

$\endgroup$
5
  • 2
    $\begingroup$ 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). $\endgroup$ Sep 30 '15 at 18:21
  • $\begingroup$ 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. $\endgroup$
    – Juan123
    Jun 4 '19 at 13:59
  • $\begingroup$ @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). $\endgroup$
    – leonbloy
    Jun 4 '19 at 14:42
  • $\begingroup$ 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$.) $\endgroup$
    – Sam OT
    Apr 15 '20 at 8:56
  • $\begingroup$ @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$ $\endgroup$
    – leonbloy
    Apr 15 '20 at 11:12

Your Answer

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