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

Question

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.

Answer 1

\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*}

Answer 2

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.