# 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

## 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. –  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