How to show inductively that $(2n)! > (n!)^2$

Question

So far I have:

Base case: $$ n = 1 : (2(1))! > (1!)^2$$ $$ 2! > 1!^2$$ $$2 > 1$$ Induction step: Assume this is true for some $n > 1$ Let n = p + 1 $$(2(p+1))! > ((p+1)!)^2$$ $$(2p)!(2p+1)(2p+2) > ((p+1)!)^2$$ $$(2p)!>\frac{((p+1)!)^2}{(2p+1)(2p+2)}$$ Now I add 1 to the smaller term in the demoninator, for cancellation purposes which makes the RHS smaller so inequality still holds.

$$(2p)!>\frac{(p!)^2(p+1)^2}{(2p+2)(2p+2)}$$ $$(2p)!>\frac{(p!)^2}{4}$$ Now I am stumped on how to get rid of the extra 4 in the denominator.

Answer 1

Use $$(2n)! = n! (n+1)(n+2)\cdots(2n)> n! \cdot 1\cdot 2 \cdots n = (n!)^2.$$

Alternatively, if you know binomial coefficients, $$ (2n)! = \binom{2n}{n} (n!)^2 > (n!)^2, $$ since $\binom{2n}{n}$ is an integer $> 1.$

Answer 2

$(2(p+1))!=(2p+2)(2p+1)(2p)!>2(p+1)(2p+1)(p!)^{2}$, now \begin{align*} 2(p+1)(2p+1)(p!)^{2}-((p+1)!)^{2}&=[2(2p+1)p!-(p+1)!](p+1)!\\ &=[2(2p+1)-(p+1)]p!(p+1)!\\ &=(3p+1)p!(p+1)!>0 \end{align*}

Answer 3

By the inductive hypothesis we have $(2n)! \geq (n!)^2$, we need to show that $(2n+2)! \geq ((n+1)!)^2$ so we need \begin{eqnarray*} (2n+2)(2n+1) \geq (n+1)^2 \\ 3n^2+4n+1 \geq 0 \end{eqnarray*} which is obviously true.

Answer 4

You are arguing the wrong way. If you start with $$(2n)!\gt (n!)^2$$ and multiply this by $(2n+2)(2n+1)$ you get $$(2(n+1))!\gt(2n+2)(2n+1)(n!)^2\gt((n+1)!)^2$$leaving you some details to fill in.

The way you are arguing at the moment attempts to deduce the result for $n$ from the result for $n+1$.

Note also that if induction is not required, the fact that the binomial coefficient $\binom {2n}n$ is a positive integer does the job. There are also various ways of proving that $\binom nr$ is a positive integer for $0\le r \le n$ including some quite simple induction methods, which would then give the result you want as a special case.