The Catalan Numbers from Their Generating Function

Deriving the expression $\displaystyle C_n = \frac{1}{n+1} \binom{2n}{n}$ for the Catalan numbers from the Catalan recurrence $\displaystyle C_{n+1} = \sum_{k=0}^n C_k C_{n-k}$ 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 $C_n$ is the number of lattice paths from (0,0) to $(n,n)$ that do not go above the diagonal $y = x$ .

Let’s define $C(x)$ to be the generating function for the Calatan numbers; i.e.,

$\displaystyle C(x) = \sum_{n=0}^{\infty} C_n x^n$ .

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

$\displaystyle \sum_{n=0}^{\infty} C_{n+1} x^n = \sum_{n=0}^{\infty} \left(\sum_{k=0}^n C_k C_{n-k}\right)x^n \\ \implies \frac{1}{x}\sum_{n=0}^{\infty} C_{n+1} x^{n+1} = C^2(x) \\ \implies \frac{1}{x}\sum_{n=1}^{\infty} C_n x^n = C^2(x) \\ \implies \frac{1}{x} \left(\sum_{n=0}^{\infty} C_n x^n - C_0 \right) = C^2(x) \\ \implies \frac{1}{x} C(x) - \frac{1}{x} = C^2(x) \\ \implies xC^2(x) - C(x) + 1 = 0 \\ \implies C(x) = \frac{1 \pm \sqrt{1 - 4x}}{2x}.$

Now, do we want the positive or the negative square root? We know that $C_0 = 1$ , so the generating function satisfies $C(0) = 1$ . Subbing in 0 for either form of $C(x)$ gives division by zero. However, $\displaystyle \lim_{x \to 0^+} C(x)$ is the indeterminate form $0/0$ for the negative square root, so let’s take a closer look at this limit. (The same limit evaluates to $\infty$ for the positive square root, so that cannot be the right choice.)

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

$\displaystyle \lim_{x \to 0^+} \frac{1 - \sqrt{1 - 4x}}{2x} = \lim_{x \to 0^+} \frac{2 (1-4x)^{-1/2}}{2} = 1.$

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

$\displaystyle C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}.$

Applying Newton’s generalized binomial series, we then have

$\displaystyle C(x) = \frac{1}{2x} \left(1 - \sqrt{1 - 4x} \right) = \frac{1}{2x} \left(1 - \sum_{n=0}^{\infty} \binom{1/2}{n} (-4x)^n \right).$

The coefficient of $x^n$ in the summand simplifies to

$\displaystyle \frac{\frac{1}{2} (\frac{1}{2}-1) \cdots (\frac{1}{2}-n+1) }{n!} (-4)^n \\ = \frac{1(1-2) \cdots (1-2n+2) }{n!} (-1)^n 2^n \\ = \frac{(-1)(-3) \cdots (-(2n-3)) }{(n!)^2} (-1)^n 2^n (n)(n-1) \cdots (1) \\ = \frac{(-1)(-3) \cdots (-(2n-3)) }{(n!)^2} (-1)^n (2n)(2n-2) \cdots (2) \\ = - \frac{(2n)!}{(n!)^2 (2n-1)} \\ = - \binom{2n}{n} \frac{1}{2n-1}.$

Therefore,
$\displaystyle C(x) = \frac{1}{2x} \left(1 + \sum_{n=0}^{\infty} \binom{2n}{n} \frac{1}{2n-1} x^n \right) \\ = \frac{1}{2x} \left(1 + -1 + \sum_{n=1}^{\infty} \binom{2n}{n} \frac{1}{2n-1} x^n \right) \\ = \frac{1}{2} \sum_{n=1}^{\infty} \binom{2n}{n} \frac{1}{2n-1} x^{n-1} \\ = \frac{1}{2} \sum_{n=0}^{\infty} \binom{2(n+1)}{n+1} \frac{1}{2n+1} x^n \\ = \sum_{n=0}^{\infty} \frac{2(n+1)(2n+1)}{2(n+1)^2}\binom{2n}{n} \frac{1}{2n+1} x^n \\ = \sum_{n=0}^{\infty} \frac{1}{n+1}\binom{2n}{n} x^n.$

Thus $\displaystyle C_n = \frac{1}{n+1}\binom{2n}{n}$ , the coefficient of $x^n$ in the generating function $C(x)$ .

References

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

9 Responses to The Catalan Numbers from Their Generating Function

Marvis says:

March 19, 2013 at 3:04 pm

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 $\infty$ and hence l’Hospital is not applicable and hence the limit is not $-1$ . 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)

- mzspivey says:
  
  March 19, 2013 at 3:09 pm
  
  Of course you’re right, Marvis. Thanks. I’ll correct that.
  
  Mike
  
John says:

February 13, 2017 at 2:39 am

How do we get C^2 (x)

it is not obvious for me.

10x

- mzspivey says:
  
  February 14, 2017 at 9:34 am
  
  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 $C(x)$ , though. I’ll go back and do that.
  
  - John says:
    
    February 14, 2017 at 2:46 pm
    
    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
  - mzspivey says:
    
    February 15, 2017 at 7:04 am
    
    It probably makes more sense if you think about it from the other direction. Calculating $C^2(x)$ involves multiplying an infinite series by itself. The result is another infinite series, but what is the coefficient of term $x^n$ in that resulting series? For example, the coefficient of $x^{10}$ is obtained by adding up all the different ways you could multiply two terms from $C(x)$ and get a term with a coefficient of $x^{10}$ . These would be $C_0 x^0 C_{10}x^{10} + C_1 x^1 C_9 x^9 + \cdots + C_{10}x^{10} C_0 x^0$ . The Cauchy product gives the formula in general.
John says:

February 15, 2017 at 4:20 pm

Thank you very much!

Best Regards,
John

shakeel says:

June 4, 2017 at 6:36 am

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.

- mzspivey says:
  
  June 4, 2017 at 7:30 am
  
  Thanks for pointing that out! The mistake was actually in the line before (forgot to multiply $C_0$ by $1/x$ ).