TAOCP 1.2.6 Exercise 46
By Eq.
Section 1.2.6: Binomial Coefficients
Exercise 46. [M21] Using Stirling's approximation, Eq. 1.2.5--(7), find an approximate value of $\binom{x+y}{y}$, assuming that both $x$ and $y$ are large. In particular, find the approximate size of $\binom{2n}{n}$ when $n$ is large.
Verified: no
Solve time: -
Solution
By Eq. (5),
$$ \binom{x+y}{y}=\frac{(x+y)!}{x!,y!}. $$
Stirling's approximation, Eq. 1.2.5--(7), states that
$$ n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n $$
when $n$ is large. Applying this approximation separately to $(x+y)!$, $x!$, and $y!$, we obtain
$$ (x+y)!\sim \sqrt{2\pi(x+y)} \left(\frac{x+y}{e}\right)^{x+y}, $$
$$ x!\sim \sqrt{2\pi x}\left(\frac{x}{e}\right)^x, \qquad y!\sim \sqrt{2\pi y}\left(\frac{y}{e}\right)^y. $$
Therefore
$$ \binom{x+y}{y} \sim \frac{ \sqrt{2\pi(x+y)} \left(\dfrac{x+y}{e}\right)^{x+y} }{ \sqrt{2\pi x}\left(\dfrac{x}{e}\right)^x \sqrt{2\pi y}\left(\dfrac{y}{e}\right)^y }. $$
The exponential factors cancel:
$$ e^{-(x+y)}\Big/e^{-x}e^{-y}=1. $$
Hence
$$ \binom{x+y}{y} \sim \sqrt{\frac{x+y}{2\pi xy}} , \frac{(x+y)^{x+y}}{x^x y^y}. $$
Thus the required approximation is
$$ \boxed{ \binom{x+y}{y} \sim \sqrt{\frac{x+y}{2\pi xy}} , \frac{(x+y)^{x+y}}{x^x y^y} }. $$
For the special case $x=y=n$,
$$ \binom{2n}{n} \sim \sqrt{\frac{2n}{2\pi n^2}} , \frac{(2n)^{2n}}{n^n n^n}. $$
Since
$$ \sqrt{\frac{2n}{2\pi n^2}} = \frac{1}{\sqrt{\pi n}}, $$
and
$$ \frac{(2n)^{2n}}{n^{2n}} = 2^{2n} = 4^n, $$
we obtain
$$ \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}. $$
Therefore the central binomial coefficient has approximate size
$$ \boxed{ \binom{2n}{n}\sim \frac{4^n}{\sqrt{\pi n}} }. $$