Proof verification for $(2n)! ≥ 2^n (n!)^2$

Question

Can someone check my proof for $(2n)! ≥ 2^n (n!)^2$ for positive integers?

• Base case $$\begin{align*}(2\cdot1)! &\geq 2^1 (1!)^2,\\ 2 &\geq 2\end{align*}$$ true for $n=1$
• Assume true for $n=k:$ $$(2k)! \geq 2^k (k!)^2.$$ Let $n = k+1.$ $$(2k+2)! ≥ 2^{k+1} \times ((k+1)!)^2.$$ By assumption, $$\begin{align*}(2k)! &\geq 2^k \times (k!)^2\\ (2k+2)! &\geq ((2^k)(k!)^2)(2k+1)(2k+2)\\ &\geq (2^k \times (k!)^2)(4k^2 + 6k +2)\\ &\geq (2^k \times (k!)^2)(12)&\text{since $k ≥ 1$}\\ &\geq 2^{k+1} \times 6 \times (k!)^2\\ &\geq 2^{k+1} \times 6 \times((k+1)(k!)/(k+1))^2\\ &\geq 2^{k+1} \times 6 \times ( (k+1)!/2)^2 &\text{since $k ≥1$}\\ &\geq 2^{k+1} \times 1.5 ((k+1)!)^2\\ &\geq 2^{k+1} \times ((k+1)!)^2.\end{align*}$$ Therefore true for $n=k+1.$

Answer 1

I would do it like this: $$(2n)!\ge2^n(n!)^2$$ $$\frac{(2n)!}{n!}\ge2^n\cdot n!$$

Notice that...

• $\frac{(2n)!}{n!}=\color{#AA0000}{2n}\color{#AA7700}{(2n-1)}\color{#AAAA00}{(2n-2)}\dots\color{#77AA00}{(n+2)}\color{#00AA00}{(n+1)}$, which has $n$ elements
• $n!=\color{#AA0000}{n}\color{#AA7700}{(n-1)}\color{#AAAA00}{(n-2)}\dots\color{#77AA00}2\cdot\color{#00AA00}1$, which also has $n$ elements

We can pair those two together like this: $$\color{#AA0000}{2n}\ge2\cdot \color{#AA0000}n$$ $$\color{#AA7700}{2n-1}\ge2\color{#AA7700}{(n-1)}$$ $$\color{#AAAA00}{2n-2}\ge2\color{#AAAA00}{(n-2)}$$ $$\dots$$ $$\color{#77AA00}{n+2}\ge2\cdot\color{#77AA00}2$$ $$\color{#00AA00}{n+1}\ge2\cdot\color{#00AA00}1$$

So, when we multiply them together: $$2n(2n-1)\dots(n+2)(n+1)\ge2^n\cdot n!$$ $$\frac{(2n)!}{n!}\ge2^n\cdot n!$$ $$(2n)!\ge2^n(n!)^2$$ Q.E.D. (cool Latin phrase meaning "proven")

Also, about your proof, I think it's slightly wrong to go from $$(2k+2)!\ge(2^k\cdot(k!)^2)(4k^2 + 6k +2)$$ $$\text{to}$$ $$(2k+2)!\ge(2^k\cdot(k!)^2)(12)\;\text{since}\;k ≥ 1$$

Hmm, why's that? It's because $k$ can be more than $1$, in which case $4k^2+6k+2$ would have a greater value.

Let me show you an example false proof

Hi! Today, I will prove that $x^2\ge\frac12x^3$ for $x\ge1$. $$x^2\ge\frac12x^3$$ $$x^2\ge\frac12\;\text{since}\;x\ge1$$ $$x\ge\sqrt\frac12$$ $$x\ge\frac12\sqrt2$$ Because $x$ can't be less than $1$, it is proven that $x^2\ge\frac12x^3$. Yeay!