# User:Bernhard Oemer/Catalan Numbers Proof

### Fifth proof

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

${\displaystyle 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 ${\displaystyle \textstyle B_{n}={2n \choose n}=d_{n}C_{n}}$ with some factor dn ≥ 1. As above, any balanced string can be uniquely decomposed into either [ c ] b or ] c+[ b, so

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

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

${\displaystyle 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 Bi = di Ci gives

${\displaystyle 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 Cn gives di = i + 1, so

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