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