Prove by induction that $(n!)^2\geq n^n$ How does one prove by induction that
$(n!)^2\geq n^n$
for  all $n \geq 1$
Hint:$(1+x)^r\geq 1+rx$
 , for $r\geq0$ and $x\geq-1$
Step 1
For $n=1$, the LHS=$1!^2=1$ and RHS=$1^1=1$. So LHS$\geq$ RHS.  
Step 2
Suppose the result be true for $n=k$  i.e.,
$(k!)^2 \geq k^k$
Step 3
For $n=k+1$
$((k+1)!)^2 \geq (k+1)^{k+1}$   
$((k+1)!)^2=(k!⋅(k+1))^2=(k!)^2(k+1)^2\geq k^k(k+1)^2$
How can I do?Thank you for help
 A: Write the LHS in two rows with first row in ascending otder and the second row in descending order.
So $(n!)^2$  is equal to
$$1\times 2\times3\times\cdots (n-1)\times n$$
$$\times$$
$$n\times(n-1)\times\cdots 2\times 1$$
Now multiply column wise (there will be $n$ columns. SO we get
$(n!)^2 = \prod_{k=1}^n \big(k\times (n+1-k)\big)$.
Now show each term of this product is at least $n$. So the full product will be at least $n^n$.
A: Might not be the shortest answer but oh well... First we start with a few lemmas:
Lemma 1: 
$$
\frac{(n+1)^{n+1}}{n^n} = (\frac{n+1}{n})^n (n+1) = (1+1/n)^n (n+1) < e(n+1) \implies \\
 (n+1)^{n+1} < n^n \cdot e(n+1)
$$
Lemma 2:
If $n \geq 2$ then $(n+1)^2 \geq e(n+1)$.  Proof is trivial. 
Now let's start the proof by induction :
Base step $n=1$ : $(1!)^2 = 1 = 1^1$
Inductive step :
$$
((n+1)!)^2 =(n! \cdot (n+1))^2 = (n!)^2 \cdot (n+1)^2 \overset{(**)}{\geq} n^n \cdot (n+1)^2 \overset{(***)}{\geq} n^n e(n+1) \overset{(****)}{\geq} (n+1)^{n+1}
$$
$(**)$ Using inductive hypothesis
$(***)$ Using Lemma 2
$(****)$ Using Lemma 1
A: Start by showing that it works for 3 (I'm starting with 3 because 1 and 2 are trivially true):
Base Case: 
We have: $(3!)^2 = 6^2 = 36$ 
We also have: $(3)^3 = 27$. So, $36 \geq 27$. Done.
Inductive Step: Assume that it works for all n.
Prove it works for all (n+1):
Let's set it up as follows: 
$\begin{align} ((n+1)!) ^2 \geq (n+1)^{n+1} \end{align}$.
By the definition of factorial, we have
$((n+1)!)^2 = ((n+1)n!)^2 = (n+1)^2(n!)^2$. 
So, now we have $(n+1)^2(n!)^2 \geq (n+1)^{n+1}$. 
If we divide both sides by $(n+1)^2$ (which we can do because this only applies where $ n \geq 0$), we get 
$(n!)^2 \geq (n+1)^{n-1}$.
So, all that's left to do is to show that $n^n  \geq (n+1)^{n-1}$ because, using the inductive hypothesis we know that $\forall n$ $ (n!)^2 \geq (n)^n $. This is almost trivial because the leading coefficient of $(n+1)^{n-1}$ is going to be $n^{n-1}$. This is obviously smaller than $n^n$ Everything else can be ignored because we know that the sum of all values $(n-1)^{n-2} + (n-2)^{n-3}...$ are going to be less than $n$. So, we finally get that
$(n!)^2 \geq n^n \geq (n+1)^{n-1}$. And we're done.
