How to compute the following recursive formula?

Question

Given:

• $f(1) = 1$
• $f(2) = 1$
• $f(k) = f(k-1)\cdot f(1) + f(k-2)\cdot f(2) + ... + f(2)\cdot f(k-2) + f(1)\cdot f(k-1)$

How does one compute the non recursive formula for $f(k)$ ?

Answer 1

Using a generating function is the best way to get the closed form for this equation. The recurrence you have defined gives the Catalan numbers which is a sequence of numbers that come up a lot in combinatorics.

You can see one decently explained proof of the recurrence here.