# 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}}\,.$$ – Batominovski Oct 22 '18 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)... – noogler Oct 22 '18 at 20:35
• @noogler If $n$ is odd just replace $n-n/2$ with $n-(n-1)/2$. – Yanko Oct 22 '18 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! – noogler Oct 23 '18 at 17:56
• @noogler it depends whether $n$ is even or odd, but you are right in general.. anyway the claim holds... – Yanko Oct 23 '18 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 ? – noogler Oct 22 '18 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 '18 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 – noogler Oct 22 '18 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 '18 at 20:44
• Thanks for the clarification ! – noogler Oct 22 '18 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.