Today i was solving a dynamic programming problem that is matrix chain multiplication and i come up with a recurrence, i tried for n=4 but :(.
How can I solve this recurrence? It is similar to the Catalan number recurrence.
$$T(n)=\begin{cases}\displaystyle\sum_{k=1}^{n−1} T(k)T(n−k) & n\ge2\\ 1 &n=1 \end{cases}$$
This is actually just the Catalan recurrence shifted by one; $T(n) = C(n-1)$.