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. 



How to solve the recursive formula $P(n)=\sum_{k=1}^{n-1}P(k)P(n-k)$
Well..., clearly $P(n) = n \frac{(2n-2)!}{n!^2}$ :).
Joke aside, here is how one can "solve" the recursion. Let's consider the generating formal power series 
$ \Phi(z) = \sum\_{n \ge 1} z^n P(n) $.


Now, let's use the recursive relation to get an equation for $\Phi$.  

$ \Phi(z) = \sum\_{n \ge 1} z^n P(n) =
 z + \sum\_{n \ge 2} z^n \sum\_{1 \le k < n} P(k)P(n-k) = \\
= z + \sum\_{k \ge 1} \sum\_{k+1 \le n} z^n P(k)P(n-k) = 
z + \sum\_{k \ge 1} z^kP(k)\sum\_{1 \le n-k} z^{n-k} P(n-k) = \\
z + \sum\_{k \ge 1} z^kP(k) (\sum\_{1 \le j} z^{j} P(j)) = 
z + \sum\_{k \ge 1} z^kP(k) \Phi(z) = \\
= z + (\sum\_{k \ge 1} z^kP(k)) \Phi(z) = z + \Phi(z)^2$ 


Thus, $\Phi(z)^2 - \Phi(z) + z = 0$. The argument can be reversed: if $\Phi$ satisfies the equation and it is of the form $\Phi(z) = z + \text{(terms with higher powers of z)} $, then the coefficients in the expansion of $\Phi$ solve the recursion for $P$. 


The solution is:
$$ \Phi(z) = \frac{1 - \sqrt{1-4z}}{2} .$$
Using the binomial theorem for the square root:
$ \Phi(z) = z - \sum\_{k \ge 2} (-4z)^k \binom{1/2}{k}$, so $ P(k) = - (-4)^k \binom{1/2}{k}$. This expression can be simplified:  

$ P(k) = - (-4)^k \frac{\prod\_{j=0}^{k-1}{(\frac{1}{2}-j)}}{k!} = 
4^k \frac{\prod\_{j=1}^{k-1}{(j - \frac{1}{2})}}{2\ k!} = 
2^{k-1} \frac{\prod\_{j=1}^{k-1}{(2j - 1)}}{k!} =
 \frac{\prod\_{j=1}^{k-1}{(2j - 1)} \prod\_{j=1}^{k-1}{(2j)} }{ k!\ (k-1)!} =\\
= \frac{ (2k-2)!}{ k!\ (k-1)!} $. 


Next, applying Stirling formula and simplifying, one gets: $ P(k) = \frac{1}{4 \sqrt{\pi}} \frac{4^k}{k^{3/2}} (1+o(1)) $.


