Generating series of Catalan numbers

Question

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.

Answer 1

Here is a possible line of attack that will give the desired result if we can prove the following (true) lemma

Lemma: For all $n>1$ $$\sum_{k=1}^{n-1} \frac{1}{k^{3/2}(n-k)^{3/2}} \leq \frac{2}{n^{3/2}}$$

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}$.

Answer 2

Let $u_N(z) = \sum_{k=0}^N C_k z^k$, a polynomial so no worries about convergence. Use the recurrence relation to show that $z u_N(z)^2 = u_N(z) -1 + O(|z|^{N+1})$. This motivates looking at the equation $z g(z)^2 = g(z) - 1$, which has solution $g(z) = (1 - \sqrt{1-4z})/(2z)$. This (after removing the removable singularity at $0$) is an analytic function in the disk $|z|<1/4$, and its Maclaurin series satisfies the same recurrence and has constant term $1$, so the coefficients are $C_k$. The radius of convergence is $1/4$ because that is the distance from $0$ to the nearest non-removable singularity.

Answer 3

The induction step of Winther only shows that $C_{n+1}<4^{n+1}/n^{3/2}$ which has the wrong denominator. The right-hand side of the lemma has to be $\frac{4}{(n+1)^{\frac{3}{2}}}-\frac{2}{n^{\frac{3}{2}}}$. The problem of the convergence of the catalan number generating function to be proved purely on the basis of the recurrence formula was proposed by Marshall Hall in his book Combinatorial Theory, p.20. He characterizes it as..."very difficult," and offers no solution.

I have now discovered that the lemma is FALSE. If n=10 the left hand side is equal to 0.15.... and the right hand side is equal to 0.063... Therefore my supposed correction is even more false. Thus, the problem continues to be unsolved...

Answer 4

Sorry to bump the thread, but I was also concerned about this issue.

I found something interesting on a paper, remanipulating Winther's arguments, to end up with a valid proof : https://arxiv.org/pdf/1511.08555.pdf (pages 4-end)

The author manages to prove $R\geqslant1/6$, which is enough to compare the generating function and $\displaystyle\frac{1-\sqrt{1-4x}}{2x}$ on the open disc $B(0,1/6)$, to then get the formula for $C_n$, and compute the exat radius afterwards (which we don't care about when we established the formula for $C_n$).

I'll leave that here for the next ones who'll need a solution.

Answer 5

Here is how you find the radius of convergence. You can use the identity

$$C_n= \frac{1}{n+1} {2n\choose n} = \frac{1}{n+1}\frac{(2n)!}{n!\,n!}$$

and the root test which gives

$$ 4 |x| < 1 \implies |x|< \frac{1}{4}. $$

See here.