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 , 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
Thus , the coefficient of in the generating function .
1. Richard Stanley, Enumerative Combinatorics, Vol. II, 2nd ed., Cambridge University Press, 2011.