The growth of the solution of the recursive relation $P(n)=\sum_{k=1}^{n-1} P(k) P(n-k)$ 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?
 A: 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)$.
A: 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)$?
