Is there an elementary proof that $x^x \geq x!$ for natural numbers $x$? I am not looking for a heuristic argument such as the one that there are $x$ terms in $x^x$ and $x!$ and since almost every term in $x \times x \times .... \times x$ is greater than almost every term in $x(x-1)(x-2)...(1)$, then $x^x \geq x!$

  • 4
    $\begingroup$ Nothing wrong with that argument! If you prefer, one can write that argument out more formally as an induction. $\endgroup$ – André Nicolas Jan 19 '15 at 19:45
  • $\begingroup$ x is real or integer? $\endgroup$ – velut luna Jan 19 '15 at 19:46
  • $\begingroup$ I was only looking to find a proof for the natural numbers. How would one go about proving it for all real numbers? $\endgroup$ – user191837 Jan 19 '15 at 19:50
  • $\begingroup$ It's not true for real numbers (where you interpret $x!$ as $\Gamma(x+1)$). For $0 < x < 1$, $x^x < \Gamma(x+1)$. $\endgroup$ – Robert Israel Jan 19 '15 at 19:53
  • $\begingroup$ You used x and you haven't stated clearly that x is a natural number. For natural numbers, I think it can be easily proved by induction. $\endgroup$ – velut luna Jan 19 '15 at 19:54

For $n=1$ is valid. $$1!\leq 1^1$$ Assume for $n$ is valid: $$n!\leq n^n$$

Multiply by $n+1$ both sides

$$(n+1)!\leq n^n(n+1)\leq(n+1)^n(n+1)=(n+1)^{n+1}$$

The last step is because if $n\leq n+1$ then $n^n\leq (n+1)^n$

  • $\begingroup$ I like this proof by induction. Thank you! $\endgroup$ – user191837 Jan 19 '15 at 20:04
  • $\begingroup$ @VarunGudibanda no problem! $\endgroup$ – rlartiga Jan 19 '15 at 20:05

Hint: Prove that $\ln \, x^x \geq \ln x!$ (for $x\geq 0.$)

Edit Since $\ln x \geq \ln i,$ for $i \leq x,$ we have $$ \ln x+\ln x +\cdots \text{ ($x$ times total)}+\ldots \geq \ln 1 +\cdots \ln x, $$ or $$x \ln x \geq \sum_{i=1}^x \ln i=\ln x!.$$

  • $\begingroup$ $xln(x) \geq \sum_{i=0}^{x-1}ln(x-i)$ and this means that $x \geq 1 + \sum_{i=1}^{x-2}\frac{ln(x-i)}{ln(x)}$ Where would I go from there? $\endgroup$ – user191837 Jan 19 '15 at 19:57
  • $\begingroup$ $x \ln x \geq \sum\limits_{x=0}^x \ln x$ $\endgroup$ – Leox Jan 19 '15 at 20:00
  • $\begingroup$ I'm still not able to see where I would proceed from here. Would I try to divide both sides by $ln(x)$? $\endgroup$ – user191837 Jan 19 '15 at 20:05
  • $\begingroup$ I added the explanation. $\endgroup$ – Leox Jan 19 '15 at 20:13
  • $\begingroup$ Ah ok. It seems obvious now that I see the solution. Thank you very much! $\endgroup$ – user191837 Jan 19 '15 at 20:15

I really wouldn't call the argument you mention "heuristic." Simply note that $$\dfrac{n^n}{n!}=\frac{n}{n} \frac{n}{n-1} \frac{n}{n-2}\cdots \frac{n}{2} \frac{n}{1}\geq 1$$ This is because every term in the product is larger than or equal to 1.


Your Answer

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