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](http://math.stackexchange.com/questions/89583/how-do-i-prove-1-frac1nn-n-by-mathematical-induction).