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

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.

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

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

-
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

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.

-
+1 for the growth factor, really nice! –  Zenon Feb 6 '12 at 4:00
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

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.

-
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

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

-

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.

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