# Prove that $n! \geq n^{\frac{n}{2}}$

I was wondering how to prove that $$n! \geq n^{\frac{n}{2}}\quad\forall n \geq 1$$ without analytic methods that relies on asympotic comparison or use of logarithms/exponentials.

Trying by induction I was stuck immediately after the induction hypothesis because I was unable to give an estimate of the following :

$$(n+1)! = n!(n+1) \geq n^{\frac{n}{2}}(n+1)$$

Is there anything I'm missing ? Any help of tip would be appreciated, as well as other methods that don't rely on seeing the inequality as an analysis task,

I'm seeking for ''arithmetic'' or ''algebraic'' demonstrations.

• Do you want to use induction? – Dr. Sonnhard Graubner Oct 12 at 8:32
• @Dr.SonnhardGraubner Not necessarily, but I was trying without analysis – jacopoburelli Oct 12 at 8:36

For $$n \ge k\ge 1$$, note that *$$k(n-k+1)-n=(n-k)(k-1) \ge 0 \implies k(n-k+1) \ge n~~~(*)$$ Next, we write $$n!=1 \cdot 2\cdot 3\cdot 4 \cdots k\cdots n ~~~(1)$$ and $$n!=n\cdot (n-1)\cdot (n-2)\cdot (n-3)\cdots (n-k+1)\cdots 1 ~~~(2).$$ Multiplying (1) and (2) pairwise as $$(n!)^2=(1\cdot n)\cdot(2\cdot (n-1))\cdot (3\cdot (n-2))\cdot (4 \cdot (n-4))\cdots (k(n-k+1))\cdots (n\cdot 1)$$ Fo from $$(*)$$, it follows that $$(n!)^2 \ge n^n.$$
If so, you have to prove that $$(n+1)!\geq (n+1)^{\frac{n+1}{2}}$$ We have $$n!(n+1)\geq n^{\frac{n}{2}}(n+1)\geq (n+1)^{(n+1)/2}$$ this is equivalent $$n^{n/2}\geq (n+1)^{(n-1)/2}$$ or $$n^n\geq (n+1)^{n-1}$$ or $$n+1\geq\left(\frac{n+1}{2}\right)^n$$ which is true.
I think you'll need one asymptotic comparison involving a famous base of exponentials, namely $$\left(1+\frac1n\right)^n\le e$$. (For what I'm about to say, you only need an upper bound of $$3$$, which is famously easier to prove.) The ratio$$\frac{(n+1)^{(n+1)/2}}{n^{n/2}}=\left(1+\frac1n\right)^{n/2}\sqrt{n+1}\le\sqrt{e(n+1)}$$is $$\le n+1$$ provided $$n\ge2$$ (so that $$n+1>e$$). So you only need check the cases $$n\in\{1,\,2\}$$, viz. the inequalities $$1!\ge1^{1/2},\,2!\ge2^{2/2}$$.
To show that $$(n+1)!\ge(n+1)^{(n+1)/2}$$, it suffices to show that \begin{align}n^{n/2}(n+1)\ge(n+1)^{(n+1)/2}&\implies n^n(n+1)^2\ge(n+1)^{n+1}\\&\implies n+1\ge\left(\frac{n+1}n\right)^n\end{align} which is true for all $$n\ge2$$ as the RHS is never greater than $$e$$. To check that case $$n=1$$, note that $$1!\ge1^{1/2}$$.