Extra material : Day 5

The extra material in this lecture was about the so-called Catalan numbers.

Definition : Let n be a non-negative integer. A Dyck path of length 2n is a path in the xy-plane from (0, 0) to (2n, 0) consisting of 2n steps, each of the form

(x, y) ↦ (x + 1, y ± 1),

which in addition never goes below the x-axis.

Definition : Let n ≥ 0. The nth Catalan number, denoted C_{n}, is defined to be the number of Dyck paths of length 2n.

Theorem 1 The Catalan numbers satisfy the following recurrence relation

C_{0} = 1,  (1)
C_{n} = ∑_{m=1}^{n} C_{m−1}C_{n−m}, ∀ n ≥ 1.  (2)

Proof : (1) is obvious. For (2) we observe that C_{m−1}C_{m−n} is the number of Dyck paths pf length 2n which first intersect the x-axis at (2m, 0).

Theorem 2

C_{n} = \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} ) .

Proof : We work with the generating function for the sequence (C_{n}), i.e.: the function

F (x) = ∑_{n=0}^{∞} C_{n}x^{n}.

Using (1) and (2) we have that

x · [F (x)]^{2} = (xF (x)) · F (x) = ( ∑_{m=1}^{∞} C_{m−1}x^{m}) · (∑_{t=0}^{∞} C_{t}x^{t})

= ∑_{n=1}^{∞} ( ∑_{m=1}^{n} C_{m−1}C_{n−m}) x^{n}

= ∑_{n=1}^{∞} C_{n}x^{n}

= F (x) − C_{0} = F (x) − 1,

i.e.:

x[F (x)]^{2} = F (x) − 1.  (3)

We may consider (3) as a quadratic equation for F (x), and hence there are two possible solutions, namely

F (x) = \frac{1 ± \sqrt{1 − 4x}}{2x}.

Since F (0) = C_{0} = 1, the correct solution must be to take the minus sign. We conclude that

F (x) = \frac{1 − \sqrt{1 − 4x}}{2x}.

To expand this in a power series, we use the binomial theorem for exponent 1/2 (which can be proven using complex analysis : note that one should not use the proof given in my solution to exercise C on homework 2, since that used the formula for C_{n} already, which means we’d be arguing in a circle !). So let’s get to it !

F (x) = \frac{1 − \sqrt{1 − 4x}}{2x}

= \frac{1}{2x} [1 − (1 − 4x)^{1/2}]

= −\frac{1}{2x} ∑_{n=1}^{∞} ( \begin{matrix}1/2 \\ n \end{matrix} ) (−4x)^{n}

= ∑_{n=0}^{∞} \frac{(−1)^{n}4^{n+1}}{2} ( \begin{matrix}1/2 \\ n + 1 \end{matrix} ) x^{n}.

So it remains to prove that, for every integer n ≥ 0,

\frac{(−1)^{n}4^{n+1}}{2} ( \begin{matrix}1/2 \\ n + 1 \end{matrix} ) = \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} ) .

To see how to prove this identity, follow the beginning of my solution to exercise C on homework 2.