Lower Bound of Central Binomial Coefficients I would like to prove by induction the following inequality:
$\frac{4^n}{n+1} < \binom{2n}{n}$, for all natural numbers n > 1.
Any hints?
 A: You know that $$\binom{2(n+1)}{n+1} = \frac{2(n+1)(2n+1)}{(n+1)^2}\binom{2n}{n}.$$
The main step of the induction proof is therefore
$$\frac{4^n}{n+1} \frac{2(n+1)(2n+1)}{(n+1)^2} \ge \frac{4^{n+1}}{n+2}.$$
This inequality is easy to show after simplification.
A: One has (see this question and this one) the identity
$$
  4^n=\sum_{i=0}^n\binom{2i}i\binom{2(n-i)}{n-i}
$$
On the right we have $n+1$ terms, if we can show that each one of them is at most $\binom{2n}n$, and at least one is strictly less, then we will have shown $4^n<(n+1)\binom{2n}n$. Now $\binom{2n}n$ counts the lattice paths across a $n\times n$ square, while $\binom{2i}i\binom{2(n-i)}{n-i}$ counts such paths that pass through the point $(i,i)$, so the required inequalities are obvious. I'm sorry I didn't use induction.
A: Note that$$\frac{\frac{4^{n+1}}{n+2}}{\frac{4^n}{n+1}}=4\frac{n+1}{n+2},$$whereas$$\frac{\frac{(2(n+1))!}{((n+1)!)^2}}{\frac{(2n)!}{n!^2}}=\frac{(2n+2)(2n+1)}{(n+1)^2}=4\frac{n+\frac12}{n+1}.$$But\begin{align}4\frac{n+1}{n+2}<4\frac{n+\frac12}{n+1}&\iff(n+1)^2<(n+2)\left(n+\frac12\right)\\&\iff n^2+2n+1< n^2+\frac52n+1\\&\iff 2n<\frac52n,\end{align}which is true for every $n$. So, the sequence $\left(\frac{2^n}{n+1}\right)_{n\in\Bbb N}$ growths strictly slower than the sequence $\left(\frac{(2n)!}{n!^2}\right)_{n\in\Bbb N}$. That's enough to prove what you want to prove.
