<s>[INST] Prove central binomial coefficient upper bound I am trying to prove that $\binom{2n}{n} < \frac{4^n}{\sqrt{2n}}$. I tried induction, but with no effect (all I can get to is $(2n+1)(2n+2) < 4\sqrt{n(n+1)}$ which is false)
 [/INST] Straight induction would be
$$
{{2n+2}\choose{n+1}}
=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}}
<\frac{2(2n+1)}{n+1} \frac{4^n}{\sqrt{2n}}
$$
So, we only have to prove that
$$
\frac{2(2n+1)}{n+1} \frac{1}{\sqrt{2n}} < \frac{4}{\sqrt{2n+2}}
$$
which unfortunately is never true.
Fortunately, straight induction works for a slightly stronger claim: 
$$
{{2n}\choose{n}}<\frac{4^n}{\sqrt{2n+1}}
$$
Indeed,
$$
{{2n+2}\choose{n+1}}=\frac{(2n+1)(2n+2)}{(n+1)(n+1)}{{2n}\choose{n}}
<\frac{2(2n+1)}{n+1}\frac{4^n}{\sqrt{2n+1}}
$$
So, we only have to prove that
$$
\frac{2(2n+1)}{(n+1)\sqrt{2n+1}}<\frac{4}{\sqrt{2n+3}}
$$
which is true for all $n\ge0$.
</s>