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}$ 
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?
 A: 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.
A: I think the best way to solve Segner's recurrence relation is to use generator functions.
A: 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.
