<s>[INST] Proving that $\binom{2n}{n} > n2^n , \forall n \ge 4 $ I'm trying to prove the following statement: $\binom{2n}{n} > n2^n ,  \forall n \ge 4 $
This is my attempt at an inductive proof:
Let $P(n)$ be the following proposition: "$\binom{2n}{n} > n2^n ,  \forall n \ge 4 $"
Base case:
$\binom{2*4}{4} = 70 > 4*2^4 = 64$ so $P(4)$ is true.
Inductive step: 
(I assume as an inductive hypothesis that P(n) is true and try to show that P(n+1) is true)
$\binom{2(n+1)}{n+1} = \binom{2n+2}{n+1} = \binom{2n+1}{n+1} + \binom{2n+1}{n}$
$= \binom{2n}{n} + \binom{2n}{n+1} + \binom{2n}{n} + \binom{2n}{n-1}$
$= 2 \binom{2n}{n} + \binom{2n}{n+1}  + \binom{2n}{n-1}$
$= 2 \binom{2n}{n} + \frac{(2n)!}{(n+1)!(2n-(n+1))!}  + \frac{(2n)!}{(n-1)!(2n-(n-1))!}$
$= 2 \binom{2n}{n} +2 \frac{(2n)!}{(n+1)!(n-1)!} $
By the inductive hypothesis we have:
$ 2 \binom{2n}{n} +2 \frac{(2n)!}{(n+1)!(n-1)!} > 2n2^n +2 \frac{(2n)!}{(n+1)!(n-1)!} = (2^{n+1}) n + 2 \frac{(2n)!}{(n+1)!(n-1)!} $
And here I'm stuck. 
If I could prove that $\frac{(2n)!}{(n+1)!(n-1)!} \ge 2^n ,  \forall n \ge 4 $ the last step would show that P(n+1) is true. But I haven't been able to prove that. Can anyone help me ?
 [/INST] You can actually do this without explicit induction.
$$\binom{2n}{n} = \frac{(2n)(2n-1)\dots(2n-(n-1))}{n(n-1)\dots2 \cdot 1} = \frac{2n}{n} \cdot \frac{2n-1}{n-1} \cdot \dots \cdot \frac{n+2}{2} \cdot \frac{n+1}{1}$$
Each of those $n$ fractions is bigger than or equal to $2$, thereby providing our $2^n$; but we can do better by noting that in fact the final two fractions come to $\frac{1}{2} (n+2)(n+1)$ which is bigger than $4n$, not just bigger than $4$, when $n > 4.56$. We could just leave it there after verifying the $n=4$ case manually, or we can do even better by accounting for the final three fractions, whereupon we have that $\frac{1}{6} (n+1)(n+2)(n+3) > 8n$ when $n > 3.66$.
So as long as there are at least a final three fractions (i.e. $n \geq 3$), and as long as $n > 3.66$, the result holds, and in fact it holds pretty massively.
</s>