I saw this recursive formula in a slide on algorithm design.

  It talks about matrix chain-multiplication, and its complexity is shown below.

  But according the recursive formula, I can't figure out the solution in the slides.

$$ P(n)= \begin{equation} \left\{ \begin{array}{lr} 1, & n=1.\\ \sum_{k=1}^{n-1}P(k)P(n-k), & n>1 \end{array} \right. \end{equation} \Rightarrow P(n)=\Omega(4^n/n^{3/2}) $$

I wonder how to get the solution, thanks a lot.

I saw this recursive formula in a slide on algorithm design. It talks about matrix chain-multiplication, and its complexity is shown below. But according the recursive formula, I can't figure out the solution in the slides.

$$ P(n)= \begin{equation} \left\{ \begin{array}{lr} 1, & n=1.\\ \sum_{k=1}^{n-1}P(k)P(n-k), & n>1 \end{array} \right. \end{equation} \Rightarrow P(n)=\Omega(4^n/n^{3/2}) $$

I wonder how to arrive at the solution shown.