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

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

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.

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.