# Combinatorial proof of a recurrence for the Catalan numbers

I would like to ask whether there is a combinatorial proof of the following recurrence relation for Catalan numbers: $$C_{n+1}=\frac{4n+2}{n+2} C_n.$$

Thanks!~

• As no motivation is given, I expect it's a curiosity question. I would suggest to look at Ira Gessel's articles discussing combinatorics of the Catalan numbers (for example, mentioned in the question mathoverflow.net/questions/26336 but also in the answer of Timothy Chow there). – Wadim Zudilin Aug 2 '10 at 11:38
• I have thought about this (out of curiosity) and I didn't come up with anything so I would be interested in any answers. – Bruce Westbury Aug 2 '10 at 12:54
• I give up: the newcomers don't care of reading the corresponding wiki pages. So, it's just losing time. For nothing. :-( – Wadim Zudilin Aug 2 '10 at 13:30
• Bruce, how many of the 66 definitions listed in Stanley's "Enumerative combinatorics" did you consider? – Victor Protsak Aug 4 '10 at 5:35
• I think giving a combinatorial proof sometimes is a bit tricky. Using not proper interpretations and methods may easily lead to a dead end. – Thomas Li Aug 4 '10 at 8:49

What you are asking is reported as fourth proof in the wiki article for the formula of the Catalan numbers: http://en.wikipedia.org/wiki/Catalan_number#Fourth_proof

• Quite nice proof. I am trying to make a bijection from the polygon interpretation to the noncrossing matching interpretation. My goal is to give a proof in the language of noncrossing matching. – Thomas Li Aug 2 '10 at 16:34
• Thanks for the first link! I could clearly understand how 'the number of different ways a convex polygon with n + 2 sides can be cut into triangles by connecting vertices with straight lines' problem is solved. I just, cant seem to understand the wiki proof! – Spai Jul 24 '12 at 8:05