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

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

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

  • $\begingroup$ @ Michael could you please elaborate more? $\endgroup$ – Devendra Jun 10 '15 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.