# Solving recurrence similar to Catalan number recurrence

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

• @Alizter could you plz tell me how to edit math eq. here? – Devendra Jun 9 '15 at 16:03
• I would recommend editing the question with your thoughts and anything you have tried so that it can gain more attention. Reference for MathJax – Ali Caglayan Jun 9 '15 at 16:04
• see wikipedia :en.wikipedia.org/wiki/Catalan_number – MATHS MOD Mar 5 '19 at 6:47

This is actually just the Catalan recurrence shifted by one; $T(n) = C(n-1)$.