7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Is there a negative radius of convergence? $\endgroup$ Jan 8, 2015 at 23:45
  • 1
    $\begingroup$ @MhenniBenghorbal "Positive" means "strictly positive". Of course. $\endgroup$
    – Etienne
    Jan 8, 2015 at 23:47
  • $\begingroup$ Perhaps "nonzero" would be the word to use. $\endgroup$
    – Théophile
    Jan 9, 2015 at 0:04
  • $\begingroup$ You may be right... $\endgroup$
    – Etienne
    Jan 9, 2015 at 0:07

5 Answers 5

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Interpreting the sum as a Riemann sum and using $\int_{\epsilon}^{1-\epsilon}\frac{dx}{(x(1-x))^{3/2}} = \frac{4(1-2\epsilon)}{\sqrt{\epsilon(1-\epsilon)}} = \frac{4}{\sqrt{\epsilon}} + \mathcal{O}(\sqrt{\epsilon})$ might be useful to prove the lemma (but have not checked if this is a viable route). $\endgroup$
    – Winther
    Jan 9, 2015 at 1:52
  • $\begingroup$ This looks exactly like what I was looking for. I'll take some time to check if I can prove the lemma. Many thanks! $\endgroup$
    – Etienne
    Jan 9, 2015 at 6:29
  • $\begingroup$ This seems to work. I'm not quite able to get the constant "2", but any constant is enough. Thanks again! $\endgroup$
    – Etienne
    Jan 9, 2015 at 7:19
  • $\begingroup$ @Etienne Very good! But any constant is not good. Note that if you try to go for $C_k \leq a 4^k/k^{3/2}$ then the ratio of the right hand side to the left hand side converges to $a\sqrt{\pi}$ so you need $a > \frac{1}{\sqrt{\pi}} \approx 0.56$ (and make sure low $n$ cases are OK). With a general $a$ you only need to show the lemma: $\sum \leq C/n^{3/2}$ where $C = 4/a-2$. Thus the largest $C$ you can use in the lemma is then $C < 4\sqrt{\pi}-2 \approx 5$. $\endgroup$
    – Winther
    Jan 9, 2015 at 7:30
  • $\begingroup$ But if you just want to show that $C_k\leq M^k/k^{3/2}$ for some constant $M$, I think this is OK if you replace $2$ by any $C$ in your Lemma and then choose $M$ appropriately. $\endgroup$
    – Etienne
    Jan 9, 2015 at 14:57
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for this answer; but this looks still a little bit cheating because it is too close to the "classical" approach outlined in the question. $\endgroup$
    – Etienne
    Jan 9, 2015 at 6:28
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I think Winther's proof is essentially correct anyway. See my last comment about it. $\endgroup$
    – Etienne
    Jun 28, 2015 at 17:47
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
8
  • 4
    $\begingroup$ No, this is cheating. I would like to show that the radius of convergence is positive without knowing the value of $C_n$. Just by using the definition. Once you have guessed the exact value of $C_n$, this is of course very easy. By the way, $C_n$ is not equal to what you wrote. $\endgroup$
    – Etienne
    Jan 8, 2015 at 23:54
  • 2
    $\begingroup$ I don't think this formula for $C_n$ is correct, anyway. $\endgroup$
    – user84413
    Jan 8, 2015 at 23:57
  • $\begingroup$ @user84413: You are right!. Thanks for the comment. $\endgroup$ Jan 9, 2015 at 0:00
  • $\begingroup$ Now, it is correct. $\endgroup$
    – Etienne
    Jan 9, 2015 at 0:01
  • 1
    $\begingroup$ @MhenniBenghorbal The OP does not want to use an explicit formula to find the radius of convergence. $\endgroup$
    – Pedro
    Jan 9, 2015 at 5:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.