# 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). Aug 2, 2010 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. Aug 2, 2010 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. :-( Aug 2, 2010 at 13:30
• Bruce, how many of the 66 definitions listed in Stanley's "Enumerative combinatorics" did you consider? Aug 4, 2010 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. Aug 4, 2010 at 8:49

## 2 Answers

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. Aug 2, 2010 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, 2012 at 8:05