2
$\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$ – Péter Komjáth Dec 3 '17 at 7:38
  • 2
    $\begingroup$ these are exactly Catalan numbers, are not they? $\endgroup$ – Fedor Petrov Dec 3 '17 at 7:54
  • 3
    $\begingroup$ @FedorPetrov Well, $P(n+1) = C(n)$. $\endgroup$ – Will Sawin Dec 3 '17 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 '17 at 9:25
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, privacy policy and cookie policy

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