Approximation for large Catalan Numbers

**usagi_killer** · September 13th 2010, 07:20 AM

Show that for a very large $m$ , $C(m) \approx \frac{4^m}{m^{\frac{3}{2}} \times \sqrt{\pi}}<br />$
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!

**emakarov** · September 13th 2010, 11:41 AM

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.

**usagi_killer** · September 13th 2010, 11:46 AM

Yup actually I figured it out after I posted haha, thanks anyway.

**usagi_killer** · September 14th 2010, 03:54 AM

Actually I think I am still a bit stuck. I did this: (After a bit of simplification)

$<br /> 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}}}<br />$

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!

**emakarov** · September 14th 2010, 06:39 AM

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

**usagi_killer** · September 14th 2010, 07:00 AM

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.

**emakarov** · September 14th 2010, 07:30 AM

Yes, this works as well.

Thread: Approximation for large Catalan Numbers

LinkBack

Thread Tools

Display

Approximation for large Catalan Numbers

Similar Math Help Forum Discussions

law of large numbers

Catalan numbers and tiling

Law of Large Numbers

Catalan Numbers

Catalan Numbers

Search Tags