20 February 2009

Why do the Catalan numbers grow like they do?

So "everybody knows" that the nth Catalan number is given by $C_n = {1 \over n+1} {2n \choose n}$, and furthermore that they have the asymptotic form
C_n = {4^n \over \sqrt{\pi n^3}} \left( 1 - {9 \over 8n} + {145 \over 128n^2} + \cdots \right)

(Okay, I'll confess: I knew the first term, and I got Maple to calculate the others just now.)

So I found myself wondering -- why this n-3/2? Let Dn = 4-n Cn. Then
{D_n \over D_{n-1}} = {2n-1 \over 2n+2} \approx 1 - {3 \over 2n}
and so we get
D_n = \prod_{k=1}^n {D_k \over D_{k-1}} \approx \exp \left( \sum_{k=1}^n -{3 \over 2k} \right)
; furthermore that sum is about -(3/2) log n, for large n, and so Dn is about n-3/2. The replacement of 1-x with exp(-x) obviously would need to be justified (and such justification would explain the presence of the mysterious π) but I'm still amused that this simple computation got the exponent.
at

3 comments:

  1. AnonymousFebruary 20, 2009 at 12:47 PM

    Can you use Stirling's formula to get the asymptotic expression?

    ReplyDelete
  2. Michael LugoFebruary 20, 2009 at 1:39 PM

    Yes, Stirling's formula will work. (More generally, I know how to derive this series without using Maple, and could post about it, but the original post was something I quickly dashed off before going to a talk and so I didn't want to get into details that would likely be incorrect.)

    ReplyDelete
  3. AnonymousFebruary 20, 2009 at 1:52 PM

    Indeed, Stirling's Formula gets you the first term, including the root pi, effortlessly.

    ReplyDelete