## amoodarya one year ago What strategies are typically used to solve these recurrences?

1. amoodarya

$f(0)=1\\f(1)=1\\f(n)=\sum_{i=1}^{n}f(i-1)f(n-i)\\$

2. amoodarya

close form of answer is $\frac{ (2n)! }{n!(n+1)! }$ but I would like to know how to arrive at this solution

3. campbell_st

4. amoodarya

it is too complicated for check and : I do not want to use " induction "

5. ParthKohli

@mukushla

6. anonymous

The symmetry of the summation is a bit suggestive. For even $$n$$, $\large\sum_{i=1}^nf(i-1)f(n-i)=2\sum_{i=1}^\frac{n}{2}f(i-1)f(n-i)$ while for odd $$n$$, $\large\sum_{i=1}^nf(i-1)f(n-i)=2\sum_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}f(i-1)f(n-i)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)^2$

7. anonymous

Suggestive of what though, not sure yet :P

8. anonymous

Some rewriting of the closed form: $\frac{(2n)!}{n!(n+1)!}=\frac{1}{n+1}\frac{(2n)!}{n!n!}=\frac{1}{n+1}\binom{2n}n$ which is the closed form for the sequence of Catalan numbers: https://en.wikipedia.org/wiki/Catalan_number

9. ParthKohli

Goddammit, I knew I'd seen that closed form before.

10. anonymous

Admittedly, we're working backwards here so it's not much help, but there's at least one proof on the wiki page.