Editing Catalan number (section)

=== Fourth proof ===

This proof uses the triangulation definition of Catalan numbers to establish a relation between {{math|''C''<sub>''n''</sub>}} and {{math|''C''<sub>''n''+1</sub>}}.

Given a polygon {{mvar|P}} with {{math|''n'' + 2}} sides and a triangulation, mark one of its sides as the base, and also orient one of its {{math|2''n'' + 1}} total edges. There are {{math|(4''n'' + 2)''C''<sub>''n''</sub>}} such marked triangulations for a given base.

Given a polygon {{mvar|Q}} with {{math|''n'' + 3}} sides and a (different) triangulation, again mark one of its sides as the base. Mark one of the sides other than the base side (and not an inner triangle edge). There are {{math|(''n'' + 2)''C''<sub>''n'' + 1</sub>}} such marked triangulations for a given base.

There is a simple bijection between these two marked triangulations:  We can either collapse the triangle in {{mvar|Q}} whose side is marked (in two ways, and subtract the two that cannot collapse the base), or, in reverse, expand the oriented edge in {{mvar|P}} to a triangle and mark its new side.

Thus
:<math>(4n+2)C_n = (n+2)C_{n+1}</math>.

Write <math>\textstyle\frac{4n-2}{n+1}C_{n-1} = C_n.</math>

Because

:<math>(2n)!=(2n)!!(2n-1)!!=2^nn!(2n-1)!!</math>

we have

:<math>\frac{(2n)!}{n!}=2^n(2n-1)!!=(4n-2)!!!!.</math>

Applying the recursion with <math>C_0=1</math> gives the result.