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?

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