Generating Functions, Catalan Approximation

Catalan Approximation

Can we find an approximation to the catalan numbers for large n? Once you approximate the binomial coefficient (n:n/2), you're home free.

Follow along as n increases step by step. When n = 2, (n:n/2) = 2. Advance to 3 and bring in a factor of 3/2. Advance to 4 and bring in a factor of 4/2. The next two steps bring in 5/3 and 6/3. The next two steps bring in 7/4 and 8/4. You see the pattern.

Divide through by 2n and get 1/2 times 3/4 times 5/6 times 7/8 etc. I'm going to take the reciprocal, because that's a bit easier. Take the log of the product, which is the sum of the logs. The log of 1+1/r is at least 1/r, and quite close to 1/r for large r. (This can be made rigorous by the taylor formulas.) Add up these logs and you are adding the odd terms of the harmonic series. The sum of the harmonics through n is very close to log(n). Go halfway, and cut the terms in half, to get the even reciprocals. This is half the log of half of n. Equivalently, it is log(sqrt(½)) + log(sqrt(n). The first term is fixed, and relatively small, so I'm going to ignore it and focus on the second. Subtract this from the log of n to get the odd terms. That leaves log(sqrt(n)). Remember that this is the log of the product of fractions, So take the exponential and write the following approximation.

(n:n/2) approximately equals 2n / sqrt(n)

Apply this to the catalan numbers and get this.

cat(n) approximately equals 4n / sqrt(2n) / (n+1)