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.
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)) $.
