Show that the $C_n \geq 4^{n-1}/2^{n}$ where $C_n$ is the Catalan number I write $C_n=\frac{1}{n+1} {2n\choose n}$ and try to prove this claim by induction. But it didn't quite work out. Any idea how to do this without much computation?
 A: Look at row $2n$ in the Pascal triangle. The sum of all $2n+1$ terms is $2^{2n}= 4^n$ . Since the central binomial coefficient is the largest number in that row, we have $4^n \le (2n+1){{2n} \choose n}$.
Hence
$$
{{2n} \choose n} \ge \frac{4^n}{2n+1}
$$
Therefore, we only need to prove that
$$
\frac{4^n}{(n+1)(2n+1)} \ge \frac{4^{n-1}}{2^n}
$$
or equivalently, that
$$
2^{n+2} \ge (n+1)(2n+1)
$$
which is much easier and follows by induction.
A: Why not induction? We have
$$C_{n+1}=\frac{1}{n+2}\binom{2n+2}{n+1}=\frac{1}{n+2}\cdot \frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}=\frac{2(2n+1)}{n+2}C_n.$$
Now all we need is the fact that $2n+1\ge n+2$.
A: By Vandermonde's identity,
$$ {2n\choose n}=\sum_{k=0}^n{n\choose k}^2$$
and for any positive integers $a_0,\dots,a_n$ we have
$$2n\sum_{i=0}^na_i^2\geq \Big(\sum_{i=0}^na_i\Big)^2$$
by Cauchy-Schwarz, hence
$$ 2n{2n\choose n}\geq 2n\sum_{k=0}^n{n\choose k}^2\geq \Big[\sum_{k=0}^n{n\choose k}\Big]^2=4^n$$
Thus we have shown that
$${2n\choose n}\geq \frac{4^n}{2n}$$
hence
$$ C_n\geq \frac{2}{n(n+1)}4^{n-1}$$
To conclude, it's enough to show that $\frac{n(n+1)}{2}\leq 2^n$ for all $n\geq 1$. This is clear for $n=1$, and for $n\geq 2$ it follows from
$$ \frac{n(n+1)}{2}={n+1\choose 2}={n\choose 1}+{n\choose 2}\leq \sum_{k=0}^n{n\choose k}=2^n$$
A: There is a simple combinatorial argument to show that $C_{n+1}\geq 2\,C_n$ for all $n=1,2,3,\ldots$.  As $C_1=1$, we can then conclude that $C_n\geq 2^{n-1}$ for all $n=1,2,\ldots$.  
Note that $C_n$ is precisely the number of sequences, called Dyck sequences, $\left(a_1,a_2,\ldots,a_{2n}\right)$ such that $a_i\in\{-1,+1\}$ and $\sum_{j=1}^i\,a_j\geq 0$ for all $i=1,2,\ldots,2n$.  Now, we can construct two disjoint sets $S_{n+1}$ and $T_{n+1}$ of Dyck sequences of length $2(n+1)$ each having $C_n$ elements, as follows.  
First, let $D_n$ denote the set of Dyck sequences of length $2n$ (whence $C_n=\left|D_n\right|$).  Take $S_{n+1}$ to be the set of all Dyck sequences of length $2(n+1)$ of the form $\left(+1,-1,a_1,a_2,\ldots,a_{2n}\right)$ with $\left(a_1,a_2,\ldots,a_{2n}\right)\in D_n$.  Now, define $T_{n+1}$ to be the set of all Dyck sequences of length $2(n+1)$ of the form $\left(+1,a_1,a_2,\ldots,a_{2n},-1\right)$ with $\left(a_1,a_2,\ldots,a_{2n}\right)\in D_n$.  Clearly, $S_{n+1}$ and $T_{n+1}$ are disjoint (because the sum of the first two entries of each sequence in $S_{n+1}$ is $0$, whereas the sum of the first two entries of each sequence in $T_{n+1}$ is $2$).  Hence, $C_{n+1}\geq \left|S_{n+1}\right|+\left|T_{n+1}\right|=C_n+C_n=2\,C_n$. 
