4
$\begingroup$

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

$\endgroup$
  • 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
6
$\begingroup$

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$

$\endgroup$
  • $\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
5
$\begingroup$

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

$\endgroup$
  • $\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
3
$\begingroup$

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.

$\endgroup$

Your Answer

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