What strategies are typically used to solve these recurrences?

Question

amoodarya · Answer

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

amoodarya · Answer

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

campbell_st · Answer

what about guess and check

amoodarya · Answer

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

parthkohli · Answer

@mukushla

anonymous · Answer

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

anonymous · Answer

Suggestive of what though, not sure yet :P

anonymous · Answer

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

parthkohli · Answer

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

anonymous · Answer

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