Exercise For each n ≥ 0, let A_{n} be the number of triangulations of an (n + 2)-gon. Prove that A_{n} = C_{n} for all n.

Solution It suffices to prove that the A_{n} satisfy the same recurrence relation as the C_{n}, namely that

A_{0} = 1,

A_{n} = ∑_{m=1}^{n} A_{m−1}A_{n−m} for all n ≥ 1.

It’s clear that A_{0} = 1. To prove the recurrence relation, label the vertices of an (n + 2)-gon as 1, 2, ..., n + 2 in some order. I claim that A_{m−1}A_{n−m} is the number of triangulations in which the edge {n + 1, n + 2} is joined to the vertex m. For the triangle {n + 1, n + 2, m} divides the remainder of the (n + 2)-gon into two halves, consisting of m + 1 and n − m + 2 vertices respectively. So, by definition, there are A_{m−1} and A_{n−m} possible triangulations of the two halves respectively. Finally, apply MP.