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!$
Asked
Active
Viewed 353 times
4
-
4Nothing wrong with that argument! If you prefer, one can write that argument out more formally as an induction. – André Nicolas Jan 19 '15 at 19:45
-
x is real or integer? – velut luna Jan 19 '15 at 19:46
-
I was only looking to find a proof for the natural numbers. How would one go about proving it for all real numbers? – Jan 19 '15 at 19:50
-
It's not true for real numbers (where you interpret $x!$ as $\Gamma(x+1)$). For $0 < x < 1$, $x^x < \Gamma(x+1)$. – Robert Israel Jan 19 '15 at 19:53
-
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. – velut luna Jan 19 '15 at 19:54
3 Answers
6
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$
rlartiga
- 4,205
- 1
- 14
- 24
5
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!.$$
Leox
- 8,120
-
$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? – Jan 19 '15 at 19:57
-
-
I'm still not able to see where I would proceed from here. Would I try to divide both sides by $ln(x)$? – Jan 19 '15 at 20:05
-
-
-
4
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.
Matt Samuel
- 58,164