Show that it is the solution of the recurrence I have to show that the solution of the recurrence $$X(1)=1, X(n)=\sum_{i=1}^{n-1}X(i)X(n-i), \text{ for } n>1$$
is $$X(n+1)=\frac{1}{n+1} \binom{2n}{n}$$
I used induction to show that.
I have done the following:
For $n=0$ : $X(1)=1 \checkmark $
We assume that it stands for each $1 \leq k \leq n$:
$$X(k)=\frac{1}{k}\binom{2(k-1)}{k-1} \ \ \ \ \ (*)$$
We want to show that it stands for $n+1$:
$$X(n+1)=\sum_{i=1}^{n} X(i)X(n+1-i)=\sum_{i=1}^{n} \frac{1}{i}\binom{2(i-1)}{i-1}\frac{1}{n+1-i}\binom{2(n-i)}{n-i}=\sum_{i=1}^{n}\frac{1}{i}\frac{(2(i-1))!}{(i-1)!(2(i-1)-(i-1))!}\frac{1}{n+1-i}\binom{(2(n-i))!}{(n-1)!(2(n-i)-(n-i))!}=\sum_{i=1}^{n}\frac{(2(i-1))!}{i!(i-1)!}\frac{(2(n-i))!}{(n-i+1)!(n-i)!}$$
How could I continue?? 
 A: These are the Catalan numbers.
This can be done by generating functions which is quite simple.
Set $X_0=0$ and $X_1=1$ and introduce 
$$f(w) = \sum_{n\ge 0} X_n w^n.$$
Because $X_0=0$ we can extend the recurrence to
$$X_n = \sum_{q=0}^n X_q X_{n-q}$$
for $n>1.$

This says that, again for $n>1,$
$$[w^n] f(w) = [w^n] f(w)^2.$$

Multiply by $w^n$ and sum over $n>1$ to get
$$\sum_{n\gt 1} w^n [w^n] f(w) =
\sum_{n\gt 1} w^n [w^n] f(w)^2.$$
This is an annihilated coefficient extractor (ACE) 
and it simplifies to
$$f(w) - X_1 w - X_0 = f(w)^2 - 2X_0 X_1 w - X_0$$
which is
$$f(w) - w = f(w)^2.$$
Solve the quadratic and pick the proper solution to finally obtain
$$f(w) = \frac{1}{2} - \frac{\sqrt{1-4w}}{2}.$$

We can  extract coefficients  from this in  various ways, by table
lookup or using Lagrange inversion. The Newton binomial series gives
$$[w^n] \sqrt{1-w} =
(-1)^n {1/2 \choose n}
\\ = (-1)^n 
\frac{1/2 \times (-1/2) \times (-3/2) \times \cdots
\times  }{n!}
= (-1)^n \frac{1}{2^n n!} \times (-1)^{n-1}
\prod_{k=0}^{n-2} (2k+1)
\\ = - \frac{1}{2^n n!} \frac{(2n-3)!}{\prod_{k=1}^{n-2} (2k)} 
= - \frac{1}{2^n n!} \frac{(2n-3)!}{2^{n-2} (n-2)!} 
= - \frac{1}{2^{2n-1} (n-1)} {2n-2\choose n-2}.$$ 
The conclusion is that
$$[w^n] f(w) = \frac{1}{2^{2n} (n-1)} 4^n {2n-2\choose n-2}
= \frac{1}{n-1} {2n-2\choose n-2}.$$
Re-write this as
$$\frac{1}{n-1} \frac{n-1}{n} {2n-2\choose n-1}
= \frac{1}{n} {2n-2\choose n-1}$$
which also holds for $n=1.$
The ACE technique is also used at this 
MSE link.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{{\rm X}\pars{1} = 1\,,\qquad\mbox{and}\qquad
     {\rm X}\pars{n} =
     \sum_{i\ =\ 1}^{n - 1}{\rm X}\pars{i}{\rm X}\pars{n - i}\,,
     \quad\mbox{for}\quad n\ >\ 1}$.

Lets $\ds{{\cal X}\pars{z} \equiv \sum_{n\ =\ 1}^{\infty}{\rm X}\pars{n}z^{n}}$,
  with $\ds{\verts{z} < {1 \over 4}}$, such that
  \begin{align}
{\cal X}\pars{z}&={\rm X}\pars{1}z + \sum_{n\ =\ 2}^{\infty}{\rm X}\pars{n}z^{n}
=z + \sum_{n\ =\ 2}^{\infty}\sum_{i\ =\ 1}^{n - 1}
{\rm X}\pars{i}{\rm X}\pars{n - i}z^{n}
\\[5mm]&=z + \sum_{i\ =\ 1}^{\infty}{\rm X}\pars{i}
\sum_{n\ =\ 1 + i}^{\infty}{\rm X}\pars{n - i}z^{n}
=z + \sum_{i\ =\ 1}^{\infty}{\rm X}\pars{i}
\sum_{n\ =\ 1}^{\infty}{\rm X}\pars{n}z^{n + i}
\\[5mm]&=z + \bracks{\sum_{i\ =\ 1}^{\infty}{\rm X}\pars{i}z^{i}}
\bracks{\sum_{n\ =\ 1}^{\infty}{\rm X}\pars{n}z^{n}}=z + {\cal X}^{2}\pars{z}
\end{align}

Then, $\ds{{\cal X}^{2}\pars{z} - {\cal X}\pars{z} + z = 0}$. This
$\ds{{\cal X}\pars{z}}$-equation has two solutions:
$\ds{1 \pm \root{1 - 4z} \over 2}$.
Since $\ds{\lim_{z\ \to\ 0}{\cal X}\pars{z} = 0}$, the $\ds{{\cal X}\pars{z}}$
correct solution is given by:
\begin{align}
{\cal X}\pars{z}&={1 - \root{1 - 4z} \over 2}
=\half\bracks{1 - \sum_{n\ =\ 0}^{\infty}{1/2 \choose n}\pars{-4z}^{n}}
=-\,\half\sum_{n\ =\ 1}^{\infty}{1/2 \choose n}\pars{-1}^{n}4^{n}z^{n}
\end{align}

which leads to
  \begin{align}{\rm X}\pars{n}&=-\,\half{1/2 \choose n}\pars{-1}^{n}4^{n}
=\pars{-1}^{n + 1}{1/2 \choose n}2^{2n - 1}
=\pars{-1}^{n + 1}\,{\Gamma\pars{3/2} \over n!\,\Gamma\pars{3/2 - n}}\,2^{2n - 1}
\\[5mm]&=\pars{-1}^{n + 1}\root{\pi}\,{1 \over n!}\,
{1 \over \Gamma\pars{3/2 - n}}\,2^{2n - 2}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\pars{1}
\end{align}

However, by using well known Gamma Function identities:
\begin{align}
\Gamma\pars{{3 \over 2} - n}&
={\pi \over \Gamma\pars{n - 1/2}\sin\pars{\pi\bracks{n - 1/2}}}
={\pi\over \bracks{\Gamma\pars{n + 1/2}/\pars{n - 1/2}}\bracks{-\cos\pars{n\pi}}}
\\[5mm]&={\pi\pars{-1}^{n + 1}\pars{n - 1/2} \over \Gamma\pars{n + 1/2}}
=\pi\pars{-1}^{n + 1}\pars{n - 1/2}\,
{\pars{2\pi}^{-1/2}2^{2n - 1/2}\Gamma\pars{n} \over \Gamma\pars{2n}}
\\[5mm]&=\root{\pi}\pars{-1}^{n + 1}2^{2n - 2}\pars{2n - 1}
\,{\pars{n - 1}! \over \pars{2n - 1}!}
=\root{\pi}\pars{-1}^{n + 1}2^{2n - 2}
\,{\pars{n - 1}! \over \pars{2n - 2}!}
\\[5mm]&=\root{\pi}\pars{-1}^{n + 1}2^{2n - 2}\,{1 \over \pars{n - 1}!}\,
{1 \over {2n - 2 \choose n - 1}}
\end{align} 

which we'll replace in expression $\pars{1}$:
  $$\color{#66f}{\large{\rm X}\pars{n}}
=\color{#66f}{\large{1 \over n}\,{2n - 2 \choose n - 1}}
\quad\imp\quad
\color{#66f}{\large{\rm X}\pars{n + 1}}
=\color{#66f}{\large{1 \over n + 1}\,{2n \choose n}}
$$

