Prove by induction: $n! \leq n^n$ for all $n \geq 1$. 
Prove by induction the inequality: $n! \leq n^n$ for all $n \geq 1$. 

I know that the base step is: for $n=1$, $1! \leq 1^1$. The induction hypothesis is: "for all $n \geq 1$ it is true that $n! \leq n^n$". In the induction step I have to prove the inequality $(n+1)! \leq (n+1)^{n+1}$, but I don't know how to prove it. 
 A: \begin{align*}(n+1)!&=(n+1)\cdot n!\\
&\leq(n+1)\cdot n^n \quad&\text{ (by induction hypothesis)}\\
&\leq (n+1)\cdot(n+1)^n \quad &\text{since } n<n+1\\
&=(n+1)^{n+1}
\end{align*}
A: The induction hypothesis is not

for all $n\ge 1$ it is true that $n!\le n^n$

because this is what you want to prove. The induction step consists in proving

for all $n\ge 1$, if $n!\le n^n$, then $(n+1)!\le(n+1)^{n+1}$

which is quite a different thing. In order to prove this, you can assume that, for a given $n$, you have $n!\le n^n$ (induction hypothesis) and, under this assumption, you have to deduce that $(n+1)!\le(n+1)^{n+1}$.
Now,
$$
(n+1)^{n+1}=(n+1)(n+1)^n \ge (n+1)n^n\ge(n+1)n!=(n+1)!
$$
The first $\ge$ is because $n+1>n$; the second $\ge$ follows from the induction hypothesis.

You could also work “backwards”. You need to prove that
$$
(n+1)^{n+1}-(n+1)!\ge0
$$
which is equivalent to prove that $(n+1)^n\ge n!$, by cancelling $n+1$. This is true because $(n+1)^n\ge n^n$ and $n^n\ge n!$ by the induction hypothesis.
