Use mathematical induction to prove $ (2n)!\geq 2^n(n!)^2$ for $n \in \mathbb{N}$

Question

I am trying to use mathematical induction to prove

$$(2n)!\ge2^n(n!)^2\quad\text{for }n\in\mathbb{N}$$

I am stuck at the $n=k+1$ point.

Answer 1

At the $k+1$ step we obtain $(2k+2)!\geq 2^{k+1}(k+1)!^2$, which is equivalent to: $(2k+2)(2k+1)(2k)!\geq 2^k2(k+1)^2(k)!^2$. By our inductive hypothesis the largest that $2^k(k)!^2$ could possibly be is $(2k)!$, so we can replace $2^k(k)!^2$ on the left hand side with $(2k)!$, and cancel the term from both sides to obtain $(2k+2)(2k+1)\geq 2(k+1)!^2$. Doing some basic algebra we obtain $4k^2+6k+2\geq 2k^2+2k+1$, which is true by inspection (note that the coefficients of the polynomial on the left hand side are all larger than those on the right hand side, and so for any $k \in \mathbb{N}$ this will hold).

Answer 2

$(2(n+1))! = (2n+2)! = (2n)!(2n+1)(2n+2) \geq 2^n\cdot (n!)^2\cdot (2n+1)(2n+2) > 2^n(n!)^2\cdot (n+1)(2n+2) = 2^{n+1}((n+1)!)^2$. Done !

Answer 3

Induction is not really needed here. Observe that $${(2n!) \over (n!)^2} = {2n \over n}{2n-1 \over n- 1} ...{n \over 1}$$ Each factor is at least $2$ so the product is at least $2^n$.

---

Hint for an inductive proof: Let $a_n = {(2n)! \over (n!)^2} $. Then $${a_{n+1} \over a_n} = {(2(n+1))! \over (2n)!} { (n!)^2 \over (n+1)!^2 }$$ $$ = { (2n + 2)(2n + 1) \over (n+1)(n+1)}$$ $$= 2{2n + 1 \over n + 1}$$ $$> 2$$ This should be highly helpful for an inductive proof.