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.
Posted by at
Labels: ,

3 comments:

Anonymous said...

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

February 20, 2009 at 12:47 PM
Michael Lugo said...

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

February 20, 2009 at 1:39 PM
Anonymous said...

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

February 20, 2009 at 1:52 PM

Post a Comment

Subscribe to: Post Comments (Atom)