The growth of the solution of the recursive relation $P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)$

Question

According to my notes,one solution of the recursive relation: $$P(n)=\sum_{k=1}^{n-1} P(k) P(n-k), \text{ for } n>1 \\ P(1)=1$$ is $\Omega(2^n) $. How do we conclude that this is one solution?

Answer 1

The claim is that the unique function $P\colon \mathbb N\to\mathbb N$ that has $P(1)=1$ and satisfies the recursion $$\tag1P(n)=\sum_{k=1}^{n-1}P(k)P(n-k)$$ is in $\Omega(2^n)$. In other words, that $P$ is not in $o(2^n)$. As a warm-up, we find that $P(2)=P(1)P(1)=1$, $P(3)=P(1)P(2)+P(2)P(1)=2$. In fact for $n\ge 3$ we have $P(n)= P(1)P(n-1)+\ldots +P(n-1)P(1)\ge 2P(n-1)$ and therefore find by induction that $$\tag2P(n)\ge2^{n-2}\qquad\text{for $n\ge 2$.}$$ This estimate would still be compatible with $P(n)\in o(2^n)$, so we need something better. And indeed we find from $(1)$ and $(2)$ for $n\ge2$ that $$\begin{align}P(n)&=\sum_{k=1}^{n-1}P(k)P(n-k)\\ &=P(1)P(n-1)+\sum_{k=2}^{n-2}P(k)P(n-k) +P(n-1)P(1)\\ &\ge 2^{n-3}+\sum_{k=2}^{n-2}2^{k-2}2^{n-k-2}+2^{n-3}\\ &=2^{n-2}+(n-3)2^{n-4}\end{align}$$ Therefore the quotient $\frac{P(n)}{2^n}\ge \frac14 + \frac{n-3}{16} $ grows beyond all bounds as $n\to\infty$, which precisely means that $P(n)\in\Omega(2^n)$.

Answer 2

Let $f(x) = P(1)+P(2)x+P(3)x^2+\cdots$. Then,

$f(x)^2 = P(1)P(1)+[P(1)P(2)+P(2)P(1)]x+[P(1)P(3)+P(2)P(2)+P(3)P(1)]x^2+\cdots$

$f(x)^2 = P(2)+P(3)x+P(4)x^2+\cdots$

$xf(x)^2 = P(2)x+P(3)x^2+P(4)x^3+\cdots$.

$1+xf(x)^2 = P(1)+P(2)x+P(3)x^2+P(4)x^3+\cdots$

$1+xf(x)^2 = f(x)$

$xf(x)^2-f(x)+1 = 0$

$f(x) = \dfrac{1 - \sqrt{1-4x}}{2x}$ (It is easy to see that the $+$ sign yields an extraneous solution.)

The radius of convergence for the power series of $f(x)$ is $\tfrac{1}{4}$. What does this tell you about $P(n)$?