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

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

• This inequality is quite weak. A stronger one is $$n!\geq n^{\frac{n}{2}}\,.$$ Oct 22, 2018 at 20:46

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$$.

• Hi thanks. But how would I prove it for odd then as for odd numbers I would have to group (n-1)(n-3)... Oct 22, 2018 at 20:35
• @noogler If $n$ is odd just replace $n-n/2$ with $n-(n-1)/2$. Oct 22, 2018 at 20:40
• Isn't it the product of n/2 + 1 elements, I tried using 6 as n and if I had n-(n/2)+1 instead of n-(n/2) it worked properly. Am I missing anything? Thanks! Oct 23, 2018 at 17:56
• @noogler it depends whether $n$ is even or odd, but you are right in general.. anyway the claim holds... Oct 23, 2018 at 19:28

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$$.

• thanks but what does ind hyp mean ? Oct 22, 2018 at 20:36
• @noogler It indicates that in that step we are using the Induction Hypotesis that is $n! ≥ (n/2)^{n/2}$.
– user
Oct 22, 2018 at 20:37
• oh okay ! Thanks ! I have been able to make sense of most of it except the last line. Is that related to binomial theorem ? Thank you for the replies Oct 22, 2018 at 20:40
• @noogler It is a well know result related to the prove of $\left(1+\frac1n\right)^{n}\to e$, you can find more information here for example.
– user
Oct 22, 2018 at 20:44
• Thanks for the clarification ! Oct 22, 2018 at 20:45

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.

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.$$