# Stirling's Approximation

A sharp Stirling's approximation form states that $$n! \sim \left(\frac{n}{e}\right)^n\sqrt{2\pi n}.$$

Use that form to show that:

$$\binom{2m}{m} = \Theta\left(\frac{2^{2m}}{\sqrt{m}}\right).$$

-
Where exactly is your difficulty? Have you substituted Stirling’s approximation into $\binom{2m}m$? – Brian M. Scott Mar 7 '13 at 5:43
How do I go about doing that? – Ben Mar 7 '13 at 6:07
You know that $\binom{2n}n=\frac{(2n)!}{n!n!}$, right? Replace each of the three factorials by its approximation. – Brian M. Scott Mar 7 '13 at 6:11
Okay, so once I do that I just factor down and prove? – Ben Mar 7 '13 at 6:14
Not quite: you have to show that the approximation is good enough to give you the $\Theta$. I’m writing up an answer to point you in the right direction. – Brian M. Scott Mar 7 '13 at 6:16

Using Stirling’s approximation, we have

\begin{align*} \binom{2n}n&=\frac{(2n)!}{n!^2}\\ &\approx\frac{\sqrt{2\pi(2n)}(2n/e)^{2n}}{\left(\sqrt{2\pi n}(n/e)^n\right)^2}\\ &=\frac{2\sqrt{\pi n}2^{2n}(n/e)^{2n}}{2\pi n(n/e)^{2n}}\\ &=\frac{2^{2n}}{\sqrt{\pi n}}\;; \end{align*}

it only remains to show that this approximation is good enough to justify the claim that $\binom{2n}n$ is $\Theta\left(\frac{2^{2n}}{\sqrt{\pi n}}\right)$. For this you have to understand that $f(n)\sim g(n)$ means that $\lim_{n\to\infty}\frac{f(n)}{g(n)}=1$. Thus, we’re given not just that $n!$ is approximately $\sqrt{2\pi n}\left(\frac{n}e\right)^n$, but that

$$\lim_{n\to\infty}\frac{n!}{\sqrt{2\pi n}\left(\frac{n}e\right)^n}=1\;.$$

Thus,

$$\frac{\frac{(2n)!}{n!^2}}{\frac{\sqrt{2\pi(2n)}(2n/e)^{2n}}{\left(\sqrt{2\pi n}(n/e)^n\right)^2}}=\frac{(2n)!}{\sqrt{2\pi(2n)}(2n/e)^{2n}}\cdot\frac{\left(\sqrt{2\pi n}(n/e)^n\right)^2}{n!^2}\to 1^2=1$$ as $n\to\infty$, i.e.,

$$\binom{2n}n\sim\frac{2^{2n}}{\sqrt{\pi n}}\;.$$

You shouldn’t have much trouble showing that if $f(n)\sim g(n)$, then $f(n)$ is $\Theta\big(g(n)\big)$, which gives you your result; just use the definitions of limit and $\Theta$.

-
Thank you so much. – Ben Mar 7 '13 at 6:39
@Ben: You’re welcome. – Brian M. Scott Mar 7 '13 at 6:40

$${2m \choose m}=\frac{(2m)!}{(m!)^2}\sim \frac{\big(\frac{2m}{e}\big)^{2m}\sqrt{4\pi m}}{({\big(\frac{m}{e}\big)^m\sqrt{2\pi m}})^2}$$ $$=2^{2m}\frac{\big(\frac{m}{e}\big)^{2m}*2\sqrt{\pi m}}{{\big(\frac{m}{e}\big)^{2m}(2\pi m)}}=\frac{2^{2m}}{\sqrt{\pi m}}$$

Since $$\color{red}{0.5}\frac{2^{2m}}{\sqrt{m}} \leq \frac{2^{2m}}{\sqrt{\pi m}} \leq\color{red}{2}\frac{2^{2m}}{\sqrt{\pi m}}$$

$${2m\choose m}\sim \frac{2^{2m}}{\sqrt{\pi m}} = \Theta\big(\frac{2^{2m}}{\sqrt{m}}\big)$$

-