# 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)= $$\left\{ \begin{array}{lr} 1, & n=1.\\ \sum_{k=1}^{n-1}P(k)P(n-k), & n>1 \end{array} \right.$$ \Rightarrow P(n)=\Omega(4^n/n^{3/2})$$

I wonder how to arrive at the solution shown.

• This may be connected to Catalan numbers: en.wikipedia.org/wiki/Catalan_number – Péter Komjáth Dec 3 '17 at 7:38
• these are exactly Catalan numbers, are not they? – Fedor Petrov Dec 3 '17 at 7:54
• @FedorPetrov Well, $P(n+1) = C(n)$. – Will Sawin Dec 3 '17 at 9:01
• The naive way to "solve" this is to compute the first few values, and then ask oeis – Goldstern Dec 3 '17 at 9:25

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