# Prove the following two statements about the Catalan numbers $C_n$

Prove the following two statements about the Catalan numbers $C_n$,

$$C_n \ge 2^{n-1}$$

and

$$C_n \ge \frac{4^{n-1}}{n^2}$$

for all all positive integers $n\ge1$. Which result is more precise.

I'm not sure at all where to go with this problem, any help is appreciated. We've covered the general Catalan formula but I am not sure how to utilize it for this problem.

• Have you covered any recurrence(s) satisfied by the Catalan numbers, or do you have only the result that $C_n=\frac1{n+1}\binom{2n}n$? – Brian M. Scott Oct 14 '15 at 19:30
• We went over Catalan number related puzzles, but no examples like the ones above, and yes we were presented with that formula. – D.Peterson Oct 14 '15 at 23:05

HINT: From the formula $C_n=\frac1{n+1}\binom{2n}n$ you can deduce the recurrence $C_{n+1}=\frac{2(2n+1)}{n+2}C_n$, with initial value $C_0=1$. Then show by induction on $n$ that

$$C_n\ge\frac{4^{n-1}}{n^2}\tag{0}$$

for $n\ge 1$. In carrying out the induction step you may find it helpful to show that

$$\frac{C_{n+1}}{C_n}\ge\frac{4^n/(n+1)^2}{4^{n-1}/n^2}\;;\tag{1}$$

use the recurrence at the top to express the lefthand side of $(1)$ as a rational function of $n$.

Next show by induction on $n$ that

$$\frac{4^{n-1}}{n^2}\ge 2^{n-1}\tag{2}$$

for $n\ge 7$. This will be easiest to do if you rewrite $(2)$ as $4^{n-1}\ge 2^{n-1}n^2$ and divide out the common factor. This together with $(0)$ immediately implies that $C_n\ge 2^{n-1}$ for $n\ge 7$, and you can check the remaining cases (i.e., $n=1,2,\ldots,6$) by actual computation.

Finally, $(2)$ says that for $n\ge 7$ the inequality $(1)$ is stronger than the inequality $C_n\ge 2^{n-1}$: in the long run (meaning for large $n$) $\frac{4^{n-1}}{n^2}$ is closer to $C_n$ than $2^{n-1}$ is, so it’s a better estimate (which I presume is what is intended here by more precise).

• I'm going to be honest. You completely lost me. I see the first induction part you did concerning n to show $C_n$ is greater than or equal to the fraction. However, after that I am not understanding what you are suggesting to do to proceed. – D.Peterson Oct 15 '15 at 6:58
• @D.Peterson: After you complete the induction proof of $(0)$, I’m saying that you should prove $(2)$ by induction starting at $n=7$. (It’s not true for $n=2,3,4,5,6$.) Then you’ll know, by combining inequalities $(0)$ and $(2)$, that $C_n\ge\frac{4^{n-1}}{n^2}\ge 2^{n-1}$ for $n\ge 7$. You’re supposed to show that $C_n\ge 2^{n-1}$ for all $n\ge 1$, so you’ll still have to check the cases $n=1,2,\ldots,6$. The last paragraph addresses the question of which inequality is more precise. That would be the one whose righthand side is closer to the real value of $C_n$, and $(2)$ says that this ... – Brian M. Scott Oct 15 '15 at 7:07
• ... is $\frac{4^{n-1}}{n^2}$ for $n\ge 7$. With this sort of estimate we’re interested in what happens in the long run, meaning for large $n$. The bound that’s tighter (closer to $C_n$) for large $n$ is the larger one, $\frac{4^{n-1}}{n^2}$. – Brian M. Scott Oct 15 '15 at 7:09