Results 1 to 7 of 7

Thread: Approximation for large Catalan Numbers

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    310

    Approximation for large Catalan Numbers

    Show that for a very large $\displaystyle m$, $\displaystyle C(m) \approx \frac{4^m}{m^{\frac{3}{2}} \times \sqrt{\pi}}
    $
    where $\displaystyle C(m)$ denotes the mth catalan number.

    So I did:

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

    Any help would be greatly appreciated!

    Thanks heaps!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    I don't agree that $\displaystyle \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Apr 2009
    Posts
    310
    Yup actually I figured it out after I posted haha, thanks anyway.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Apr 2009
    Posts
    310
    Actually I think I am still a bit stuck. I did this: (After a bit of simplification)

    $\displaystyle
    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 $\displaystyle e$ does not cancel and there is an extra $\displaystyle \sqrt{m+1}$

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

    Thanks!
    Last edited by usagi_killer; Sep 14th 2010 at 04:12 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Represent $\displaystyle C(m)$ as $\displaystyle (2m)!/((m+1)(m!)^2)$ and don't modify m+1. Then, after replacing the factorials by their Stirling approximations, note that $\displaystyle (m+1)\sqrt{m}\sim m^{3/2}$. Here $\displaystyle f(n)\sim g(n)$ means $\displaystyle \lim_{n\to\infty}f(n)/g(n)=1$.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Apr 2009
    Posts
    310
    Thanks again, actually I noticed another cool method, is this way also acceptable?

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

    $\displaystyle \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 \displaystyle{\approx \frac{4^me}{\sqrt{\pi} m^{\frac{3}{2}} \left(\frac{m+1}{m}\right)^{m+\frac{3}{2}}}}$

    $\displaystyle \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 \displaystyle{\left(1+\frac{1}{m}\right)^m}$ approachs e. Formally we can write, $\displaystyle \displaystyle{\lim_{m \to \infty} \left(1+\frac{1}{m}\right)^m = e}$

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

    So substituting these back in yields:

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

    $\displaystyle \displaystyle{\approx \frac{4^m}{\sqrt{\pi} \times (m)^{\frac{3}{2}}}}$ as required.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    Yes, this works as well.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. law of large numbers
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Feb 12th 2011, 11:39 AM
  2. Catalan numbers and tiling
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 21st 2010, 10:50 PM
  3. Law of Large Numbers
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Aug 2nd 2009, 11:53 PM
  4. Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 11th 2008, 07:51 AM
  5. Catalan Numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 1st 2008, 04:38 AM

Search Tags


/mathhelpforum @mathhelpforum