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).$$
 A: 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$.
A: $${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)$$
