# Approximation for large Catalan Numbers

Printable View

• Sep 13th 2010, 08:20 AM
usagi_killer
Approximation for large Catalan Numbers
Show that for a very large $m$, $C(m) \approx \frac{4^m}{m^{\frac{3}{2}} \times \sqrt{\pi}}
$

where $C(m)$ denotes the mth catalan number.

So I did:

$C(m) = \frac{1}{m+1} \binom{2m}{m} = \frac{(2m)!}{(m+1)!m!} = \frac{(2m)(2m-1)(2m-2)}{m!}$ after some canceling.

Now $\lim_{m \to \infty} \frac{(2m)(2m-1)(2m-2)}{m!}$ and I'm stuck here... we are given Stirling's approximation formula $n! \approx \sqrt{2\pi n} \times \left(\frac{n}{e}\right)^n$ for $n >>>>1$ but I do not know how to apply that here to my final step...

Any help would be greatly appreciated!

Thanks heaps!
• Sep 13th 2010, 12:41 PM
emakarov
I don't agree that $\frac{(2m)!}{(m+1)!m!} = \frac{(2m)(2m-1)(2m-2)}{m!}$ unless m = 4.

I would recommend not to simplify (2m)!/((m+1)m!m!) but instead to apply Stirling's formula to replace each factorial.
• Sep 13th 2010, 12:46 PM
usagi_killer
Yup actually I figured it out after I posted haha, thanks anyway.
• Sep 14th 2010, 04:54 AM
usagi_killer
Actually I think I am still a bit stuck. I did this: (After a bit of simplification)

$
C(m) \approx \frac{4^me^{-2m}}{\sqrt{\pi}m^{-m}(m+1)^{m+\frac{3}{2}}e^{-2m-1}} \approx \frac{4^me}{\sqrt{\pi}m^{-m}(m+1)^{m+\frac{3}{2}}}
$

But in the end the $e$ does not cancel and there is an extra $\sqrt{m+1}$

I've checked all my simplifications, they are all correct, how do I get rid of the $e$ and $\sqrt{m+1}$ to match what's required?

Thanks!
• Sep 14th 2010, 07:39 AM
emakarov
Represent $C(m)$ as $(2m)!/((m+1)(m!)^2)$ and don't modify m+1. Then, after replacing the factorials by their Stirling approximations, note that $(m+1)\sqrt{m}\sim m^{3/2}$. Here $f(n)\sim g(n)$ means $\lim_{n\to\infty}f(n)/g(n)=1$.
• Sep 14th 2010, 08:00 AM
usagi_killer
Thanks again, actually I noticed another cool method, is this way also acceptable?

$\displaystyle{\approx \frac{4^me}{\sqrt{\pi}m^{-m}(m+1)^{m+\frac{3}{2}}}}$

$\displaystyle{\approx \frac{4^me}{\sqrt{\pi} m^{\frac{3}{2}}m^{-\left(m+\frac{3}{2}\right)}(m+1)^{m+\frac{3}{2}}}}$

$\displaystyle{\approx \frac{4^me}{\sqrt{\pi} m^{\frac{3}{2}} \left(\frac{m+1}{m}\right)^{m+\frac{3}{2}}}}$

$\displaystyle{\approx \frac{4^me}{\sqrt{\pi}m^{\frac{3}{2}}\left(1+\frac {1}{m}\right)^m\left(1+\frac{1}{m}\right)^{\frac{3 }{2}}}}$

Now note as m gets large $\displaystyle{\left(1+\frac{1}{m}\right)^m}$ approachs e. Formally we can write, $\displaystyle{\lim_{m \to \infty} \left(1+\frac{1}{m}\right)^m = e}$

Also note as m gets large $\displaystyle{\left(1+\frac{1}{m}\right)^{\frac{3} {2}}}$ approaches 1. Formally we can write, $\displaystyle{\lim_{m \to \infty} \left(1+\frac{1}{m}\right)^{\frac{3}{2}} = 1}$

So substituting these back in yields:

$\displaystyle{\approx \frac{4^me}{\sqrt{\pi}m^{\frac{3}{2}}e(1)}}$

$\displaystyle{\approx \frac{4^m}{\sqrt{\pi} \times (m)^{\frac{3}{2}}}}$ as required.
• Sep 14th 2010, 08:30 AM
emakarov
Yes, this works as well.