1
$\begingroup$

How can I find an asymptotically equivalent function for $\ln \binom{n^2}{2n}$?

I think I need to use the definition of the binomial coefficient and Stirling's approximation, but I'm not sure what to do after this.

$\endgroup$
1
  • $\begingroup$ Where did you get to after using Stirling and the binomial coefficient? That expression may actually be fully simplified even though it may look complicated. $\endgroup$ Oct 2 '19 at 9:03
2
$\begingroup$

In the same spirit an in answer and comment, we can even get a very good approximation.

Writing $$\binom{n^2}{2 n}=\frac{(n^2)!}{(2n)! \, (n^2-2n)!}$$ $$\log \left(\binom{n^2}{2 n}\right)=\log\left((n^2)!\right)-\log\left((2n)!\right)-\log\left((n^2-2n)!\right)$$ Using Stirling approximation $$\log(p!)=p (\log (p)-1)+\frac{1}{2} \left(\log (2 \pi )+\log \left({p}\right)\right)+\frac{1}{12 p}-\frac{1}{360 p^3}+O\left(\frac{1}{p^5}\right)$$ apply to each term and continue with Taylor series for large values of $n$. This should give $$\log \left(\binom{n^2}{2 n}\right)=2 n \left(\log (n)+\log \left(\frac{e}{2}\right)\right)-\log \left(2 e^2 \sqrt{\pi }\right)-\log{(\sqrt n)}-\frac 3 {8n}+O\left(\frac{1}{n^2}\right)$$

As shown below, this is even quite good for very small values of $n$ $$\left( \begin{array}{ccc} n & \text{approximation} & \text{exact} \\ 3 & 4.49297 & 4.43082 \\ 4 & 9.49277 & 9.46265 \\ 5 & 15.0177 & 14.9999 \\ 6 & 20.9595 & 20.9478 \\ 7 & 27.2466 & 27.2383 \\ 8 & 33.8286 & 33.8224 \\ 9 & 40.6676 & 40.6628 \\ 10 & 47.7345 & 47.7306 \end{array} \right)$$

$\endgroup$
2
$\begingroup$

By Stirling approximation $n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$ we have that

$$ \binom{n^2}{2n}=\frac{n^2!}{(2n)!(n^2-2n)!}\sim \frac{\sqrt{2 \pi n^2}\left(\frac{n^2}{e}\right)^{n^2}}{\sqrt{2 \pi 2n}\left(\frac{2n}{e}\right)^{2n}\sqrt{2 \pi (n^2-2n)}\left(\frac{n^2-2n}{e}\right)^{n^2-2n}}$$

$$\sim\frac{\sqrt{2 \pi }n^{2n^2+1}e^{-n^2}}{2\sqrt \pi n^\frac12 2^{2n}n^{2n}e^{-2n}\cdot \sqrt{2 \pi}nn^{2n^2-4n}e^{-n^2+2n}}=$$

$$=\frac1{2\sqrt \pi} \cdot {n^{2n-\frac12}} \cdot 2^{-2n} $$

and therefore

$$\ln \binom{n^2}{2n}\sim n\ln n$$

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