3
$\begingroup$

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

$\endgroup$
5
  • 4
    $\begingroup$ Where exactly is your difficulty? Have you substituted Stirling’s approximation into $\binom{2m}m$? $\endgroup$ Mar 7, 2013 at 5:43
  • $\begingroup$ How do I go about doing that? $\endgroup$
    – Ben
    Mar 7, 2013 at 6:07
  • $\begingroup$ You know that $\binom{2n}n=\frac{(2n)!}{n!n!}$, right? Replace each of the three factorials by its approximation. $\endgroup$ Mar 7, 2013 at 6:11
  • $\begingroup$ Okay, so once I do that I just factor down and prove? $\endgroup$
    – Ben
    Mar 7, 2013 at 6:14
  • $\begingroup$ 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. $\endgroup$ Mar 7, 2013 at 6:16

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @Ben: You’re welcome. $\endgroup$ Mar 7, 2013 at 6:40
1
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.