Proof by induction that Catalan number $C_n$ is less or equal to $n!$

Question

In positive integer range,

I want to prove that Catalan(n) is always the same or smaller than Factorial(n) by using mathematical induction.

Answer 1

Hint (using your comment above): Note that $3!=3\cdot 2!=2!+2!+2!$. This can be compared directly, term-for-term, with your expression for $C(3)$ (using that $C(2)\leq 2!$, $C(1)\leq 1!$ and $C(0)\leq 0!$).

If you use (strong) induction, set up a similar relation for general $n$, and compare term-by-term, you can conclude.

Answer 2

This holds for $0 \leq n \leq 2$. Catalan(n) is $\frac{1}{n+1}{{2n} \choose n}$. It follows that the ratio of Catalan(n+1) to Catalan(n) is $\frac{4n+2}{n+2}$. We have $\frac{4n+2}{n+2} < n +1$ implies $n > 1$, and the result follows.