Deriving the expression for the Catalan numbers from the Catalan recurrence is a classic exercise in generating function manipulation, although the details are sometimes omitted in textbooks (and on the Wikipedia page). This post fills in the details.

The Catalan numbers are the solution to many combinatorial problems. See, for example, this selection from Vol. II, Chapter 6, of Stanley’s *Enumerative Combinatorics* [1], as well as the Catalan addendum, for many such combinatorial interpretations. My favorite is that is the number of lattice paths from (0,0) to that do not go above the diagonal .

Let’s define to be the generating function for the Calatan numbers; i.e.,

.

To derive a closed-form for from the recurrence, start by multiplying both sides of the Catalan recurrence by and summing up:

Now, do we want the positive or the negative square root? We know that , so the generating function satisfies . Subbing in 0 for either form of gives division by zero. However, is the indeterminate form for the negative square root, so let’s take a closer look at this limit. (The same limit evaluates to for the positive square root, so that cannot be the right choice.)

Applying l’Hôpital’s rule, we have

The negative square root does evaluate to the correct number, so that one must be the right choice for :

Applying Newton’s generalized binomial series, we then have

The coefficient of in the summand simplifies to

Therefore,

Thus , the coefficient of in the generating function .

**References**

1. Richard Stanley, *Enumerative Combinatorics*, Vol. II, 2nd ed., Cambridge University Press, 2011.

### Like this:

Like Loading...

*Related*

That is a very nice derivation of the generating function and the relation to binomial coefficients. Just a small correction. The limit for the positive square-root will be and hence l’Hospital is not applicable and hence the limit is not . Hence, you can directly discard it. Also, interestingly, I encountered Catalan again last week in my answer [here](http://math.stackexchange.com/questions/326714/need-help-proving-this-integration/326825#326825)

Of course you’re right, Marvis. Thanks. I’ll correct that.

Mike

How do we get C^2 (x)

it is not obvious for me.

10x

I’m using the formula for term-by-term multiplication of an infinite series, sometimes called the

Cauchy product. I realize now that I didn’t define , though. I’ll go back and do that.10x for the answer but i would like to know how sum c(k)*c(n-k) leads to C^2

Thank you in advance

It probably makes more sense if you think about it from the other direction. Calculating involves multiplying an infinite series by itself. The result is another infinite series, but what is the coefficient of term in that resulting series? For example, the coefficient of is obtained by adding up all the different ways you could multiply two terms from and get a term with a coefficient of . These would be . The Cauchy product gives the formula in general.

Thank you very much!

Best Regards,

John

Hi, two lines before the “Now, do we want the positive or the negative square root?” (second last line) you multiplied the equation by ‘x’ but the ‘1’ remained. It should be ‘x.

Thanks for pointing that out! The mistake was actually in the line before (forgot to multiply by ).