User:Bernhard Oemer/Catalan Numbers Proof

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Fifth proof[edit]

This proof is based on the Dyck words interpretation of the Catalan numbers, so Cn is the number of ways to correctly match n pairs of brackets. We denote a (possibly empty) correct string with c and its inverse (where [ and ] are exchanged) with c+. Since any c can be uniquely decomposed into c = [ c1 ] c2, summing over the possible spots to place the closing bracket immediately gives the recursive definition

Now let b stand for a balanced string of length 2n containing an equal number of [ and ] and with some factor dn ≥ 1. As above, any balanced string can be uniquely decomposed into either [ c ] b or ] c+[ b, so

Also, any incorrect balanced string starts with c ], so

Subtracting the above equations and using Bi = di Ci gives

Comparing coefficients with the original recursion formula for Cn gives di = i + 1, so