1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Brian M. Scott Oct 14 '15 at 19:30
  • $\begingroup$ We went over Catalan number related puzzles, but no examples like the ones above, and yes we were presented with that formula. $\endgroup$ – D.Peterson Oct 14 '15 at 23:05
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.Peterson Oct 15 '15 at 6:58
  • $\begingroup$ @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 ... $\endgroup$ – Brian M. Scott Oct 15 '15 at 7:07
  • $\begingroup$ ... 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}$. $\endgroup$ – Brian M. Scott Oct 15 '15 at 7:09

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.