1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This inequality is quite weak. A stronger one is $$n!\geq n^{\frac{n}{2}}\,.$$ $\endgroup$ – Batominovski Oct 22 '18 at 20:46
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hi thanks. But how would I prove it for odd then as for odd numbers I would have to group (n-1)(n-3)... $\endgroup$ – noogler Oct 22 '18 at 20:35
  • $\begingroup$ @noogler If $n$ is odd just replace $n-n/2$ with $n-(n-1)/2$. $\endgroup$ – Yanko Oct 22 '18 at 20:40
  • $\begingroup$ 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! $\endgroup$ – noogler Oct 23 '18 at 17:56
  • $\begingroup$ @noogler it depends whether $n$ is even or odd, but you are right in general.. anyway the claim holds... $\endgroup$ – Yanko Oct 23 '18 at 19:28
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ thanks but what does ind hyp mean ? $\endgroup$ – noogler Oct 22 '18 at 20:36
  • $\begingroup$ @noogler It indicates that in that step we are using the Induction Hypotesis that is $n! ≥ (n/2)^{n/2}$. $\endgroup$ – user Oct 22 '18 at 20:37
  • $\begingroup$ 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 $\endgroup$ – noogler Oct 22 '18 at 20:40
  • $\begingroup$ @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. $\endgroup$ – user Oct 22 '18 at 20:44
  • $\begingroup$ Thanks for the clarification ! $\endgroup$ – noogler Oct 22 '18 at 20:45
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.