Trying to prove : $n! ≥ (n/2)^{n/2}$

Question

I am trying to prove : $n!\ge (n/2)^{n/2}$

I have tried proof by induction and it gets stuck after expanding the powers to something like : $(k+1/2)^{k/2} + (k+1/2)^{1/2}$. Is there any other way to prove this or should I keep trying to prove by induction ?

I also tried : $n(n-1)..1$ and then pairing the elements to create $n/2$ terms but got stuck there as well. I have proved $n! \le n^n$ (could that help me prove this ? )

Any help/guidance is appreciated. Thanks

Answer 1

You don't need a proof by induction.

Recall that $n! = n(n-1)(n-2)...1$

If you only take the first $n/2$ elements you get (assuming $n$ is even for simplicity but this works for odd value too)

$n(n-1)...(n-n/2)$ This is a product of $n/2$ elements each of them is larger than $n/2$.

Answer 2

As noticed we don't need induction since the result can be obtained in a simpler way, anyway it can be instructive show also how proceed by induction, notably we have

• base case: $n=1 \implies 1\ge \frac{\sqrt 2}2$
• induction step: assuming true $n! ≥ (n/2)^{n/2}$ we need to prove that $(n+1)! ≥ ((n+1)/2)^{(n+1)/2}$

therefore we have

$$(n+1)! =(n+1)n!\stackrel{Ind. Hyp.}\ge (n+1)(n/2)^{n/2}\stackrel{?}\ge((n+1)/2)^{(n+1)/2}$$

that is

$$(n+1)(n/2)^{n/2}\stackrel{?}\ge((n+1)/2)^{(n+1)/2}$$

$$(n+1)^2(n/2)^{n}\stackrel{?}\ge((n+1)/2)^{(n+1)}$$

$$(n+1)n^{n}\stackrel{?}\ge \frac12(n+1)^{n}$$

$$n+1\stackrel{?}\ge \frac12\left(1+\frac1n\right)^{n}$$

which is true since $\left(1+\frac1n\right)^{n}<3$.

Answer 3

We have $$(n!)^2=(1\cdot n)\,\big(2\cdot (n-1)\big)\,\cdots\,\big((n-1)\cdot 2\big)\,(n\cdot 1)\,.$$ For each $k=1,2,\ldots,n$, we see that $$k\cdot (n+1-k)=n-(n-k)(k-1)\geq n\,.$$ Consequently, $$(n!)^2\geq n^n\text{ or }n!\geq n^{\frac{n}{2}}>\left(\frac{n}{2}\right)^{\frac{n}{2}}\text{ for each }n=1,2,3,\ldots\,.$$

---

We can also show that $$k\cdot (n+1-k)=\left(\frac{n+1}{2}\right)^2-\left(k-\frac{n+1}{2}\right)^2\leq \left(\frac{n+1}{2}\right)^2$$ for all $k=1,2,\ldots,n$. This gives $$n!\leq \left(\frac{n+1}{2}\right)^n\,.$$ Thus, under the convention that $0^0:=1$, we have $$n^{\frac{n}{2}}\leq n! \leq \left(\frac{n+1}{2}\right)^n\text{ for every }n\in\mathbb{Z}_{\geq 0}$$ with the equality cases $n=0$ and $n=1$ for the inequality on the the right-hand side, and with the equality cases $n=0$, $n=1$, and $n=2$ for the inequality on the left-hand side.

Answer 4

In fact $n^{\frac{n}{2}}\leq n!$ holds for $n=1,2,\dots.$

My proof:

It is sufficient to prove $\frac{n}{2}\log n\leq\log 1+\dots +\log n$ holds for $n=1,2,\dots.$
Since $\log x + 1$ is an increasing function on $(0,\infty)$, \begin{align*}n\log n=\int_{1}^{n}(\log x+1)\,dx &<(\log 2 + 1)+\dots+(\log n + 1)\\&=(\log 1+\dots+\log n) + (n-1)\end{align*} holds for $n=2,3,\dots.$
So, $$n\log n\leq (\log 1+\dots+\log n)+(n-1)$$ holds for $n=1,2,\dots.$
Next we prove that $$n-1<\log 1+\dots +\log n$$ holds for $n=4,5\dots$ by induction.
WolframAlpha says $4-1=3<\log 4!=\log 24$ holds.
Let $k\geq 4$.
Assume that $$k-1<\log 1+\dots +\log k$$ holds.
Then, $$k=(k-1)+1<(\log 1+\dots\log k) +1<\log 1+\dots+\log k+\log (k+1).$$
So, $$n-1<\log 1+\dots +\log n$$ holds for $n=4,5\dots$.
Therefore, $$n\log n\leq (\log 1+\dots+\log n)+(n-1)<2(\log 1+\dots+\log n)$$ holds for $n=4,5,\dots.$
And,
$1\log 1=2\log 1,$
$2\log 2=2(\log 1 + \log 2),$
$3\log 3=\log 27<\log 36=2(\log 1+\log 2+\log 3).$
Therefore, $$n\log n\leq 2(\log 1+\dots+\log n)$$ holds for $n=1,2,\dots.$
Therefore, $$\frac{n}{2}\log n\leq \log 1+\dots+\log n$$ holds for $n=1,2,\dots.$