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