Exercise 1528Combinatorics › Binomial coefficientsL1Added 3 Nov 2026

Catalan via binomial

#Catalan#binomial#generating function

Statement

Show that the Catalan numbers $C_n=\frac{1}{n+1}\binom{2n}{n}$ satisfy the recurrence $C_{n+1}=\sum_{k=0}^{n}C_kC_{n-k}$ .

Hint

Split a Dyck path by first return to the axis.

Show solutionHide solution

Solution

First return. A Dyck path of length $2(n+1)$ has a first return to the axis at step $2(k+1)$ . The prefix is an "elevated" Dyck path of length $2k$ , and the suffix is a Dyck path of length $2(n-k)$ .

Count. Number of prefixes of length $2k$ in elevated form: $C_k$ . Suffix: $C_{n-k}$ . So $C_{n+1}=\sum_k C_kC_{n-k}$ .

Conclusion. The Catalan recurrence holds.

Catalan via binomial

Statement

Solution

More problems in Binomial coefficients