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?

Solution 1:

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

Solution 2:

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