The Catalan numbers, defined byform the sequence 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,...

The Catalan numbers, defined by

form the sequence 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. They first appeared in 1838 when Eugène Catalan (1814–1894) showed that there are Cn ways of parenthesizing a nonassociative product of n + 1 factors. [For instance, when n = 3 there are five ways: ((ab)c)d, (a(bc))d, a((bc)d), a(b(cd)), (ab)(ac).] For n ≥ 1, prove that Cn can be given inductively by