Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Problem Prove that $n! > \sqrt{n^n}, n \geq 3$.

I'm currently have two ideas in mind, one is to use induction on $n$, two is to find $\displaystyle\lim_{n\to\infty}\dfrac{n!}{\sqrt{n^n}}$. However, both methods don't seem to get close to the answer. I wonder is there another method to prove this problem that I'm not aware of? Any suggestion would be greatly appreciated.

share|improve this question
2  
possible duplicate of How do you prove that $n^n$ is $O(n!^2)$? –  lhf Feb 5 '12 at 23:30

5 Answers 5

up vote 36 down vote accepted

$(n!)^2 = (n \times 1) \times ((n-1)\times 2) \times \cdots \times (1 \times n) \gt n^n$

since $(n-1)\times 2 = 2n-2 \gt n$ iff $n \gt 2$.

Then take the square root.

share|improve this answer
    
very nice. just wrote the same thing... –  Amihai Zivan Feb 5 '12 at 22:48
    
That trick does the job ;) Thank you. –  Chan Feb 5 '12 at 22:49

You can prove by induction (a-la Gauss) that $n! = 1 \cdots n = (1 \cdot n)(2 \cdot (n-1))(3 \cdot (n-2))\cdots(n/2(n/2+1)) \geq n^{(n/2)}$ and that finishes the proof.

share|improve this answer
3  
This proof is good (+1) (it is essentially Henry's proof). However, I see no induction. –  robjohn Feb 6 '12 at 0:38
    
the induction is to actually show that (n-k)(k+1)>=n for every natural k. –  Amihai Zivan Feb 6 '12 at 7:20

To show that $(n!)^2>n^n$ for all $n\geq 3$ by induction, you first check that $(3!)^2>3^3$. Then to get the inductive step, it suffices to show that when $n\geq 3$, $(n+1)^2\geq\frac{(n+1)^{n+1}}{n^n}=(n+1)\left(1+\frac{1}{n}\right)^n$. This is true, and in fact $\left(1+\frac{1}{n}\right)^n<3$ for all $n$. It would be more than enough to use $\left(1+\frac{1}{n}\right)^n<n$, which is proved in another thread.

share|improve this answer
    
This is a minor variant of André Nicolas's answer (written independently). –  Jonas Meyer Feb 6 '12 at 5:30

There can be no method prettier than Henry's pairing argument. So let's work in the opposite direction, and look for an ugly argument.

When we go from $n$ to $n+1$, the factorial function grows by a factor of $n+1$. What about the other function? It grows by the factor $$\frac{\sqrt{(n+1)^{n+1}}}{\sqrt{n^n}},$$ which simplifies to $$(n+1)^{1/2}\left(1+\frac{1}{n}\right)^{n/2}.$$ Recall that $(1+1/n)^n<3$. So if $n+1>3$, the second function grows by a factor that is less than the growth factor of the factorial function. Now we hunt for a place >$2$ at which $n!>\sqrt{n^n}$. Beyond it, everything will be OK.

Another way: Next we look at estimates, in an attempt to carry our your other proposed argument. It is easier to work with logarithms. We want to show that if $n$ is large enough, then $\log(n!)> \frac{1}{2}n\log n$.

Draw the curve $y=\log x$. Draw the rectangle with base $[1,2]$ and height $\log 2$, the rectangle with base $[2,3]$ and height $\log 3$, and so on up to the rectangle with base $[n-1,n]$ and height $\log n$. The sum of the areas of these rectangles is $\log 1+\log 2+\cdots+\log n$. By comparison with the area under the curve $y=\log x$ from $1$ to $n$, we conclude that $$\log(n!) > \int_1^n \log x\,dx =n\log n -n +1.$$ (The integration is not hard, one does it by parts, letting $u=\log x$ and $dv=dx$.)

Now it is enough to show that $n\log n -n+1 >\frac{1}{2}n\log n$, or equivalently that $\frac{1}{2}n\log n -n+1>0$, if $n$ is large enough. Making sure that $\frac{1}{2}\log n >0$ will do the job, but we can do better because we get some help from the $1$.

The integral estimate we got for $\log(n!)$ can be refined quite a bit. After all the refinements are done, we obtain the Stirling approximation to $n!$, a result of great importance.

share|improve this answer
1  
+1 for the growth factor, really nice! –  Zenon Feb 6 '12 at 4:00
1  
I don't find the "growth factor" approach ugly, since it provides a technique adaptable to other cases. +1 from me. –  Francesco Feb 6 '12 at 10:15

$\log$ is strictly concave $\left(\frac{\mathrm{d}^2}{\mathrm{d}x^2}\log(x)=-\frac{1}{x^2}<0\right)$, so for $1\le k\le n$, we have $$ \log(k)\ge\frac{(k-1)\log(n)+(n-k)\log(1)}{n-1}\tag{1} $$ with equality only when $k=1$ or $k=n$. Summing $(1)$ yields $$ \begin{align} \log(n!) &\ge\frac{n}{2}(\log(n)+\log(1))\\ &=\log(\sqrt{n^n})\tag{2} \end{align} $$ If $n\ge3$, then for at least one of the summands, equality fails; therefore, $$ n!>\sqrt{n^n}\tag{3} $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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