# Catalan Numbers in Pascal's Triangle

Tony Foster found concealed presence of the Catalan numbers in Pascal's triangle:

The $n$th Catalan number $\displaystyle C_{n}=\frac{1}{n+1}{2n \choose n}$ could be discovered in the following combination:

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

or, more explicitly,

$\displaystyle C_{n}=\frac{(2n-3)!}{(n-1)!(n-2)!}+\frac{(2n-2)!}{n!(n-2)!}-\frac{(2n-3)!}{n!(n-3)!}-\frac{(2n-2)!}{(n+1)!(n-3)!}$

For $n=5,$ the positive terms are in blue, the negative ones in orange:

Let's prove the identity.

\displaystyle \begin{align} C_{n}&=\bigg[\frac{(2n-3)!}{(n-1)!(n-2)!}-\frac{(2n-3)!}{n!(n-3)!}\bigg]+\bigg[\frac{(2n-2)!}{n!(n-2)!}-\frac{(2n-2)!}{(n+1)!(n-3)!}\bigg]\\ &=\frac{(2n-3)!}{(n-1)!(n-3)!}\bigg[\frac{1}{n-2}-\frac{1}{n}\bigg]+\frac{(2n-2)!}{n!(n-3)!}\bigg[\frac{1}{n-2}-\frac{1}{n+1}\bigg]\\ &=2\frac{(2n-3)!}{n!(n-2)!}+3\frac{(2n-2)!}{(n+1)!(n-2)!}\\ &=\frac{(2n-3)!}{n!(n-2)!}\bigg[2+\frac{3(2n-2)}{n+1}\bigg]\\ &=\frac{(2n-3)!}{n!(n-2)!}\frac{4(2n-1)}{n+1}\\ &=\frac{(2n-3)!}{(n+1)!(n-2)!}\frac{2\cdot (2n-2)(2n-1)}{n-1}\\ &=\frac{2(2n-1)!}{(n+1)!(n-1)!}\\ &=\frac{(2n)!}{(n+1)!n(n-1)!}=\frac{(2n)!}{(n+1)!\space n!}=C_{n}. \end{align}

For other $n,$ the quadruples meander, or may be the right term "percolate", downwards forming a wavy pattern.

Note: Another - simpler and better known - way may be found in [Grimaldi, 154-155]. It is illustrated by the diagram below:

Again, the orange entries are subtracted from the adjacent blue ones. As can be verified,

$\displaystyle\frac{(2n)!}{n!\space n!}-\frac{(2n)!}{(n+1)!\space (n-1)!}=\frac{(2n)!}{n!\space (n-1)!}\bigg[\frac{1}{n}-\frac{1}{n+1}\bigg]=\frac{(2n)!}{(n+1)!\space n!}=C_{n}.$

There are two more ways of obtaining the Catalan numbers as differences; these are shown below:

that is,

$\displaystyle\frac{(2n+1)!}{(n+1)!\space n!}-\frac{(2n+1)!}{(n+2)!\space (n-1)!}=\frac{(2n+1)!}{(n+1)!\space (n-1)!}\bigg[\frac{1}{n}-\frac{1}{n+2}\bigg]=\frac{2(2n+1)!}{(n+2)!\space n!}=C_{n+1}.$

and

because,

\begin{align}\displaystyle \frac{(2n)!}{n!\space n!}-\frac{(2n)!}{(n+2)!\space (n-2)!}&=\frac{(2n)!}{n!\space (n-2)!}\bigg[\frac{1}{n(n-1)}-\frac{1}{(n+1)(n+2)}\bigg]\\ &=\frac{(2n)!}{n!\space (n-2)!}\bigg[\frac{4n+2}{n(n-1)(n+1)(n+2)}\bigg]\\ &=\frac{2(2n+1)!}{(n+2)!\space n!}=\frac{(2n+2)!}{(n+2)!\space (n+1)!}=C_{n+1}. \end{align}

Tony Foster came up with an additional pattern:

In general, the pattern is $\displaystyle {2n+1\choose n+1}+{2n\choose n+2}-{2n\choose n+1}-{2n+1\choose n+2}.$ Let's check,

\begin{align}\displaystyle {2n\choose n+1}-{2n\choose n+2}&=\frac{(2n)!}{(n+1)!(n-1)!}-\frac{(2n)!}{(n+2)!(n-2)!}\\ &=\frac{(2n)!}{(n+1)!(n-2)!}\bigg[\frac{1}{n-1}-\frac{1}{n+2}\bigg]\\ &=\frac{3(2n)!}{(n+2)!(n-1)!}. \end{align}

For the other pair:

\begin{align}\displaystyle {2n+1\choose n+1}-{2n+1\choose n+2}&=\frac{(2n+1)!}{(n+1)!n!}-\frac{(2n+1)!}{(n+2)!(n-1)!}\\ &=\frac{(2n+1)!}{(n+1)!(n-1)!}\bigg[\frac{1}{n}-\frac{1}{n+2}\bigg]\\ &=\frac{2(2n+1)!}{(n+2)!n!}. \end{align}

Now, taking the difference of the two:

\begin{align}\displaystyle \frac{2(2n+1)!}{(n+2)!n!}-\frac{3(2n)!}{(n+2)!(n-1)!}&=\frac{(2n)!}{(n+2)!(n-1)!}\bigg[\frac{2(2n+1)}{n}-\frac{3}{1}\bigg]\\ &=\frac{(2n)!}{(n+2)!(n-1)!}\frac{n+2}{n}\\ &=\frac{(2n)!}{(n+1)!n!}\\ &=\frac{1}{n+1}\frac{(2n)!}{n!n!}=C_{n}. \end{align}

Is there any relationship between all these patterns?

### References

1. R. Grimaldi, Fibonacci and Catalan Numbers: an Introduction, Wiley, 2012