Prove Segner's Recurrence Relation $C_{n+1} = \sum\limits_{i=0}^n C_i C_{n-i}$ on Catalan Numbers $C_n = \frac{1}{n+1} \binom{2n}{n}$

Question

Prove Segner's Recurrence Relation $C_{n+1} = \sum\limits_{i=0}^n C_i C_{n-i}$ on Catalan Numbers $C_n = \frac{1}{n+1} \binom{2n}{n}$

Plugging in the Catalan Equation, we want to prove:

\begin{align*} \frac{1}{n+2} \binom{2(n+1)}{n+1} &= \sum\limits_{i=0}^n \frac{1}{i+1} \binom{2i}{i} \frac{1}{n-i+1} \binom{2(n-i)}{n-i} \\ \end{align*}

Expanding the binomial coefficients to factorials (again this is a formula we want to prove, not a result we have demonstrated):

\begin{align*} \frac{1}{n+2} \frac{(2n+2)!}{(n+1)!(n+1)!} &= \sum\limits_{i=0}^n \frac{1}{i+1} \frac{(2i)!}{i!i!} \frac{1}{n-i+1} \frac{(2n-2i)!}{(n-i)!(n-i)!} \\ \end{align*}

How would one go from here?

Answer 1

In all honesty, I’d prove it combinatorially, e.g., by showing that there are $\frac1{n+1}\binom{2n}n$ well-formed strings of $n$ pairs of parentheses and that the number of such strings satisfies the recurrence. (Using generating functions is also a reasonable approach.)

You said that you’re familiar with the first fact. As for the second, if $s$ is such a string, split it into two substrings at the first point at which the initial segment is well-formed. Say that you have $\ell$ pairs in that initial segment and $n−\ell$ in the final segment. There are $C_{n−\ell}$ possibilities for the final segment. Try to see why there are $C_{\ell−1}$ possibilities for the initial segment; use the fact that it’s the minimal well-formed prefix.

Answer 2

I think the best way to solve Segner's recurrence relation is to use generator functions.

Answer 3

As somebody suggested the method of generating functions is good. We have:

\begin{eqnarray} g(x)&:=&\sum\limits_{i=0}^\infty \binom{2 i}{i} \frac{x^i}{i+1}\\ &=& \frac{1}{x} \int_0^x \sum\limits_{i=0}^\infty \binom{2 i}{i} \xi^i d\xi\\ &=& \frac{1}{x} \int_0^x \frac{d \xi}{\sqrt{1-4 \xi}} \\ &=& - \frac{-1+\sqrt{1-4 x}}{2 x} \end{eqnarray} Now we square and then invert. We have: \begin{eqnarray} g(x)^2 &=& -\frac{1}{2} \sum\limits_{n=2}^\infty \binom{1/2}{n} (-4)^n x^{n-2}\\ &=& -\frac{1}{2} \sum\limits_{n=0}^\infty \binom{1/2}{n+2} (-4)^{n+2} x^n \end{eqnarray} Now we just need to simplify the coefficient. We have:

\begin{eqnarray} &&-\frac{1}{2} \binom{1/2}{n+2} (-4)^{n+2} = \\ &&-\frac{1}{2} \frac{\prod\limits_{j=0}^{n+1} (1/2-j)}{(n+2)!} (-4)^{n+2} = \\ &&-\frac{1}{2} \frac{1}{2^{n+2}} (-1)^{n+1} \frac{(2n+2)!}{(2n )!! (n+2)!} (-4)^{n+2} = \\ && \frac{(2n+2)!}{(n+1)!(n+2)!} \end{eqnarray}

As expected.