- #1
mathmari
Gold Member
MHB
- 5,049
- 7
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)
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)