The Catalan numbers may be defined as follows: $C_0=1$ and
$$C_{n+1}=\sum_{k=0}^n C_k C_{n-k}\, .$$
One way to compute these numbers is to introduce the generating series $f(x)=\sum_{n\geq 0} C_n x^n$. After some formal manipulations, one gets that $f(x)$ is the same as the power series for $\frac{1-\sqrt{1-4x}}{2x}\cdot$ This allows to compute $C_n$ explicitely, namely $C_n=\frac{(2n)!}{n!(n+1)!}\cdot$ From this formula, one infers quite easily that the radius of convergence of the series $f(x)$ is indeed positive, so that all the formal manipulations are justified a posteriori. (Of course, there is no need to do that if one is ready to use formal series; but let's say that one is trying to build an exercise for undergraduate students).
Now, here is the question:
Does anybody know how to prove directly that $f(x)$ has a positive radius of convergence, using only the above definition of the Catalan numbers?
Note that if one knows the combinatorial interpretation of the $C_n$'s as the number of expressions containing $n$ pairs of parentheses which are correctly matched, then it is rather obvious that $C_n\leq \left(\begin{matrix} 2n\\ n\end{matrix} \right)\leq 4^n$, and everything is OK. But I would like to have a "purely analytical" proof.
Best Answer
Here is a possible line of attack that will give the desired result if we can prove the following (true) lemma
Assume $C_k \leq \frac{4^k}{k^{3/2}}$ for $k=1,2,\ldots, n$ then
$$C_{n+1} \leq 4^{n}\left(\frac{2}{n^{3/2}} + \sum_{k=1}^{n-1} \frac{1}{k^{3/2}(n-k)^{3/2}}\right) \leq \frac{4^{n+1}}{(n+1)^{3/2}}$$
by the above lemma and the assumed bound on $C_k$ follows by induction. This result gives
$$\left|\sum_{k=0}^n C_k x^k\right| \leq 1 + \sum_{k=1}^n \frac{(4x)^k}{k^{3/2}}$$
and it follows that the series converges for $|x| < \frac{1}{4}$.