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?? 

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.
