2
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Could you explain me the first equality ? It doesn't seem algebraic to me $\endgroup$ – jacopoburelli Oct 12 at 9:15
  • $\begingroup$ @Jacopoburelli Sorry! there was a typo which I have corrected in this edit. $\endgroup$ – Dr Zafar Ahmed DSc Oct 12 at 9:28
  • 1
    $\begingroup$ Definitely the most elementary and purely "arithmetic-algebraic" solution. (+1) $\endgroup$ – trancelocation Oct 12 at 9:38
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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