User:Bernhard Oemer/Catalan Numbers Proof

Fifth proof

This proof is based on the Dyck words interpretation of the Catalan numbers, so C_n 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 = [ c₁ ] c₂, summing over the possible spots to place the closing bracket immediately gives the recursive definition

$C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0.$

Now let b stand for a balanced string of length 2n containing an equal number of [ and ] and $\textstyle B_{n}={2n \choose n}=d_{n}C_{n}$ with some factor d_n ≥ 1. As above, any balanced string can be uniquely decomposed into either [ c ] b or ] c⁺[ b, so

$B_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}.$

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

$B_{n+1}-C_{n+1}=\sum _{i=0}^{n}{2i+1 \choose i}C_{n-i}=\sum _{i=0}^{n}{\frac {2i+1}{i+1}}B_{i}C_{n-i}.$

Subtracting the above equations and using B_i = d_i C_i gives

$C_{n+1}=2\sum _{i=0}^{n}d_{i}C_{i}C_{n-i}-\sum _{i=0}^{n}{\frac {2i+1}{i+1}}d_{i}C_{i}C_{n-i}=\sum _{i=0}^{n}{\frac {d_{i}}{i+1}}C_{i}C_{n-i}.$

Comparing coefficients with the original recursion formula for C_n gives d_i = i + 1, so

$C_{n}={\frac {1}{n+1}}{2n \choose n}.$