For integer $n>2$, $(n!)^2 > n^n$ Problem: For integer $n>2$, show that $(n!)^2 > n^n$ 
My attempt: I tried using induction. For $n=3$, the given condition is satisfied. Let us suppose $k!^2>k^k$ for some $k\geq3$.
Then, $(k+1)!^2 =k!^2(k+1)^2> k^k(k+1)^2$
Thus if I can somehow show that $k^k(k+1)^2\geq(k+1)^{k+1}$,  i.e., $k^k\geq(k+1)^{k-1}$,  I am done.
Any hints/suggestions are welcome. Any non-inductive proofs are also allowed
 A: Carl Friedrich Gauss would have solved this aged 7. 
$$\begin{align}
n!^2 &= (1 \times 2 \times 3 \dots \times n) \times (1 \times 2 \times 3 \dots \times n) \\
&= (1 \times n) \times (2 \times (n-1)) \times (3 \times (n-2))\times \dots \times (n \times 1)
\end{align}$$
The first and last of the $n$ factors are $n$, the others are all greater than $n$, therefore the product is greater than $n^n$ if $n > 2$. 
A: Note that the integral
$$ \int_{1}^{n} \log x\, dx = n \log n - n + 1 $$
can be bounded above by the sum
$$ \sum_{k=2}^{n} \log k = \log(n!) $$
so, taking logarithms, it suffices to prove that $ 2 n \log n - 2n + 2 > n \log n $ for $ n > 2 $. We then have to show $ n \log n > 2n - 2 $. Define $ f(x) = x \log x - 2x + 2 $ and take derivatives to find $ f'(x) = \log x - 1 $, which implies that $ f(x) $ is increasing for all $ x \geq 3 $. We have $ f(5) = 5 \log 5 - 8 \approx 0.04 > 0 $, so this proves the result for all $ n \geq 5 $. For $ n = 3, 4$, we may verify the claim directly:
$$ 36 = (3!)^2 > 3^3 = 27 $$
$$ 24^2 > 16^2 \Rightarrow (4!)^2 > 4^4 $$
A: For your induction argument,
$$
k^k\geq(k+1)^{k-1}\iff\left(\frac{k}{k+1}\right)^k\geq\frac{1}{k+1}\iff\left(1-\frac{1}{k+1}\right)^k\geq\frac{1}{k+1}.
$$
But the last inequality above holds because of Bernoulli's inequality:
$$
\left(1-\frac{1}{k+1}\right)^k\geq 1-\frac{k}{k+1}=\frac{1}{k+1}.
$$
A: A non induction proof. It's enough to show that
$$
1<\frac{1^2}{n}\times\frac{2^2}{n}\times\cdots\times\frac{n^2}{n}.
$$
First, suppose $n=2k$, $k\geq 1$. Then it's enough to show $\frac{j(n+1-j)}{n}\geq 1$ for all $j=1,\ldots,k\;$ and the inequality is strict for some $j$. Consider
$$
j(n+1-j)-n=j(2k+1-j)-2k=(j-1)(2k-j)
$$
which is $\geq 0$ for all $j$ and $>0$ for $j\neq 1$. 
For $n=2k+1$, $k\geq 1 $, we only need to worry about the extra factor $\frac{(k+1)^2}{n}=\frac{(k+1)^2}{2k+1}$ which is clearly $> 1$ via the expansion $(k+1)^2=k^2+2k+1$.
A: Two observations at the outset will make an inductive proof fairly straightforward. Note that
$$
\binom{k}{\ell}<k^\ell,\qquad2\leq\ell\leq k\tag{1}
$$
an inequality that is easier to verify than you might think. Also note that
$$
(k+1)^k=k^k+\binom{k}{1}k^{k-1}+\sum_{\ell=2}^k\binom{k}{\ell}k^{k-\ell}<2k^{k}+\sum_{\ell=2}^kk^\ell\cdot k^{k-\ell}=(k+1)k^k\tag{2}
$$
by the binomial theorem. Hence,
\begin{align}
[(k+1)!]^2&= [(k+1)k!]^2\\[1em]
&= (k+1)^2(k!)^2\\[1em]
&> (k+1)^2\cdot k^k\tag{inductive hypothesis}\\[1em]
&= (k+1)[(k+1)k^k]\\[1em]
&> (k+1)(k+1)^k\tag{by $(2)$}\\[1em]
&= (k+1)^{k+1},
\end{align}
as desired.
