# Factorial (Proof by Induction)

Prove by induction that $n!<n^n$ for all $n>1$. So far I have (using weak induction):

1. Base Case: Proved that claim holds for $n=2$
2. Induction hypothesis: For some arbitrary $n>1, n!<n^n$
3. Need to show that $n!\cdot(n+1)<(n+1)^{n+1}$
4. 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!

-
Must you do this by induction? It's obvious otherwise. –  Calvin Lin Jan 31 '13 at 0:04

$(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.
It suffices to show that $k+1 < \frac {(k+1)^{k+1} } {k^k}$. This is obvious since $k+1 > k$, so $\frac {(k+1)^{k+1} } {k^k} = (k+1) \left( \frac {k+1}{k} \right) ^k > k+1$.
Note, you can show this directly, since $n \geq i$ for $i\leq n$.