Proving the Solution of a Recurrence Relation Using Induction

[mathmari]

Hey!

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?? (Wondering)

 

[mathmari]

Do we have to use maybe a formula from combinatorics, for example $$\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{m}^2$$ ?? (Wondering)