<s>[INST] Proof of the inequality $2^{n} < \binom{2n}{n} < 2^{2n}$? As review for a midterm I am asked to prove the inequality:
$2^{n} < \binom{2n}{n} < 2^{2n}, n > 1.$
What I have is a two-part inductive proof. It is not hard to show for $2^{n} < \binom{2n}{n}$:
Base step:
Let $n=2$:
$2^{2} < \frac{(2n)!}{2!2!} < 2^{2*2}$
$4 < 6 < 16$
Inductive Step:
Show $2^{k+1} < \frac{[2(k+1)]!}{(k+1)!(k+1)!}.$
We have
$2^{k+1} = 2^{k}*2,$
so
$2^{k+1} < 2 * \frac{2k!}{k!k!}.$
Since
$\frac{(2k+2)!}{(k+1)*k!*(k+1)*k!} = \frac{2(k+1)*(2k+1)*2k!}{(k+1)k!(k+1)k!} = (2k+1) * \frac{2k!}{k!k!}$
and
$(2k+1) > 2, k \geq 2,$
we can conclude the first part of the inequality. However, I can't make the second part work. By similar algebra I arrive at:
$(2k+1) * \frac{2k}{k!k!} < 2^{2(k+1)} = 2^{2k}*2^{2},$
but
$ (2k+1) \nless 4, k \geq 2.$
What have I done wrong?
 [/INST] Another approach. Using the Stirling's approximation we have $$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\leq n!\leq n^{n+\frac{1}{2}}e^{1-n}
 $$ hence $$\dbinom{2n}{n}=\frac{\left(2n\right)!}{n!^{2}}\leq\frac{e}{\sqrt{2}\pi n^{1/2}}4^{n}<\color{red}{4^{n}}
 $$ and $$\frac{\left(2n\right)!}{n!^{2}}\geq\frac{\sqrt{\pi}2^{2n+1}}{n^{1/2}e^{2}}>\color{red}{2^{n}}.$$
</s>