Show that for any integer $n\ge5$, the inequality ${2n \choose n}>3^n$ holds. I used induction, but got stuck at the last step. By cancelling common factors in the expanded $2n$ choose $n$, I got a simpler equation that didn't make sense.How do i prove this inequality?
 A: The main step is to prove for $n+1$ then
$${2(n+1)\choose n+1}=\frac{(2n+2)!}{(n+1)!(n+1)!}=\frac{(2n+2)(2n+1)}{(n+1)^2}{2n\choose n}=\frac{2(2n+1)}{(n+1)}{2n\choose n}$$
Using the hypothesis
$${2(n+1)\choose n+1}>\frac{2(2n+1)}{(n+1)}\cdot 3^n$$
but
$$\frac{2(2n+1)}{n+1}=\frac{4n+2}{n+1}=\frac{3(n+1)+(n-1)}{n+1}=3+\frac{n-1}{n+1}>3$$
so,
$${2(n+1)\choose n+1}>\frac{2(2n+1)}{(n+1)}\cdot 3^n>3\cdot 3^n=3^{n+1}$$
A: Here's a slightly goofier approach:
By the binomial theorem, we have $4^n=\sum_{k=0}^{2n} \binom{2n}{k}$. Since $\binom{2n}{n}$ is the largest of these $2n+1$ summands, it is at least as large as the average of the summands. So $\binom{2n}{n} \geq \frac{4^n}{2n+1}$.
I claim that $\frac{4^n}{2n+1}>3^n$ for all $n \geq 11$. This can be proved by induction: it is true for $n=11$, and if it is true for some fixed $n\geq 11$, then
$$
\frac{4^{n+1}}{3^{n+1}}=\frac{4}{3}\frac{4^n}{3^n}>\frac{4}{3}(2n+1)>2n+3
$$
(this last inequality holds for all $n \geq 3$).
So the result is true for $n \geq 11$. It only remains to check that it is true for $n=5,6,7,8,9,10$, which is a straightforward computation.
A: Since $\binom{2m+2n}{m+n}\ge\binom{2m}m\binom{2n}n,$ the set $\{n:\binom{2n}n\ge3^n\}$ is closed under addition. Therefore, in order to show that the inequality holds for all $n\ge5,$ it's enough to verify it for $n=5,6,7,8,9.$
A: Two useful identities:
$$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$
$$\binom{n}{k} = \binom{n}{n-k}$$
Applied here.
$$\binom{2n+2}{n+1}=\frac{2n+2}{n+1}\binom{2n+1}{n}=\frac{2n+2}{n+1}\binom{2n+1}{n+1}=\frac{(2n+2)(2n+1)}{(n+1)^2}\binom{2n}{n}$$
Then just get lower bounds
$$\frac{(2n+2)(2n+1)}{(n+1)^2} \geq 3$$
which is straight forwards.
A: Let $a=\frac{(2n)!}{n!n!}$. Given that $a>3^n$ show $\frac{(2n+1)(2n+2)}{(n+1)^2}a > 3^{n+1}$. 
$\frac{4n^2+7n+2}{n^2+2n+1}a > 3*3^n$. Since $a>3^n$ it is sufficient to show that $\frac{4n^2+7n+2}{n^2+2n+1} > 3$. $$
4n^2+7n+2 > 3n^2+6n+3$$$$
n^2+n-1 > 0$$
which is clearly true for $n\geq 5$
