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
- R. Grimaldi, Fibonacci and Catalan Numbers: an Introduction, Wiley, 2012

Pascal's Triangle and the Binomial Coefficients
- Binomial Theorem
- Arithmetic in Disguise
- Construction of Pascal's Triangle
- Dot Patterns, Pascal Triangle and Lucas Theorem
- Integer Iterations on a Circle
- Leibniz and Pascal Triangles
- Lucas' Theorem
- Lucas' Theorem II
- Patterns in Pascal's Triangle
- Random Walks
- Sierpinski Gasket and Tower of Hanoi
- Treatise on Arithmetical Triangle
- Ways To Count
- Another Binomial Identity with Proofs
- Vandermonde's Convolution Formula
- Counting Fat Sets
- e in the Pascal Triangle
- Catalan Numbers in Pascal's Triangle
- Sums of Binomial Reciprocals in Pascal's Triangle
- Squares in Pascal's Triangle
- Cubes in Pascal's Triangle
- Pi in Pascal's Triangle
- Pi in Pascal's Triangle via Triangular Numbers
- Ascending Bases and Exponents in Pascal's Triangle
- Determinants in Pascal's Triangle
- Tony Foster's Integer Powers in Pascal's Triangle

|Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
72256921