3
$\begingroup$

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.

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

1 Answer 1

11
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.