How to solve the recursive formula $P(n)=\sum_{k=1}^{n-1}P(k)P(n-k)$ 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.  
 A: 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))  $.
