Prove by induction that $n!<n^n$ for all $n>1$.
So far I have (using weak induction):
- Base Case: Proved that claim holds for $n=2$
- Induction hypothesis: For some arbitrary $n>1, n!<n^n$
- Need to show that $n!\cdot(n+1)<(n+1)^{n+1}$
- Induction step…
$n! < n^n$ [induction hypothesis]
$(n+1) \cdot n!<n^n(n+1)$ [multiply both sides by $(n+1)$]
$(n+1)!< n^{n+1}+n^n$
This is where I'm stuck. I'm not sure if I went wrong somewhere, or if I'm just approaching it the wrong way.
Thanks for any feedback!
Best Answer
$(n+1)n!<(n^n)(n+1)<((n+1)^n)(n+1)=(n+1)^{(n+1)}$. Try to direct your algebraic manipulations so that the expressions gradually look like the desired result.