Use induction to prove that $n! \leq n^{n-1}$ Use induction to prove that $n! \leq n^{n-1}$ for all integers $n\geq 1$. I'm having a hard time with induction and my professor said this is a good future test like question if someone can post a solution and explain it would help me out a lot. Thank you.
 A: Call $n!\le n^{n-1}$ the statement $T(n)$.
$T(1)$ holds, because $1!\le 1^{1-1}=1^0=1$.  
Now assume $T(n)$, i.e. $n!\le n^{n-1}$.
Then $$(n+1)!=n!(n+1)\le n^{n-1}(n+1)\le (n+1)^{n-1}(n+1)=(n+1)^n$$  
So $T(n+1)$ holds too.
We've proved $T(1)$ and that $\forall n\in\mathbb N(T(n)\implies T(n+1))$. $\ \ \ \square$
A: Induction or not,
$$n! = 1\cdot 2\cdot 3\cdot\ldots\cdot n \leq 1\cdot n\cdot n\cdot\ldots\cdot n = n^{n-1}.$$
A: Hint $\,\ $ $\dfrac{n^{n-1}}{n!}=\, \dfrac{n}{n}\,\dfrac{n}{n\!-\!1}\cdots \dfrac{n}{3}\,\dfrac{n}{2}\, \ge\, 1,\,$ being a product of rationals $\ge 1$.
Remark $ $ This proof can be discovered purely mechanically by writing $\, {\rm f}(n)\, =\, \dfrac{n^{n-1}}{n!}\,$ as a telescoping product of its successive quotients $\rm\,f(k)/f(k\!-\!1)\,$ as below.
Multiplicative Telescopy
$\ \ \rm\displaystyle  f(a\!-\!1) \prod_{\large k\,=\,a}^{\large n} \dfrac{f(k)}{f(k-1)}\, =\ f(n) $ 
Proof $ $ Induct on $\rm\,n.\,$ Base is $\rm\, f(a\!-\!1)\frac{f(a)}{f(a-1)}=\,f(a)\,$ at $\rm\,n=a.\,$ Inductive step $\rm\,n\to n\!+\!1\,$ is
$\quad\ \displaystyle\rm  f(a\!-\!1)\prod_{\large k\,=\,a}^{\large n+1}\dfrac{f(k)}{f(k\!-\!1)}\, =\, \left[f(a\!-\!1)\prod_{\large k\,=\,a}^{\large n}\dfrac{f(k)}{f(k\!-\!1)}\right]\dfrac{f(n\!+\!1)}{f(n)}\, =\, \color{brown}{f(n)}\dfrac{f(n\!+\!1)}{\color{brown}{f(n)}} \, =\, f(n\!+\!1) $
Remark $\ $ Unwinding the induction yields a vivid depiction of the telescopic cancellation
$\quad \rm\displaystyle f(a\!-\!1)\prod_{\large k\,=\,a}^{n} \frac{f(k)}{f(k\!-\!1)}\,  =   \ \frac{\color{#c00}{\rlap{---}f(a\!-\!1)}}{1}\frac{\color{green}{\rlap{--}f(a)}}{\color{#C00}{\rlap{---}f(a\!-\!1)}}\frac{\color{royalblue}{\rlap{---}f(a\!+\!1)}}{\color{green}{\rlap{--}f(a)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{---}f(a\!+\!1)}}\, \cdots\,  \frac{\color{brown}{\rlap{---}f(n\!-\!1)}}{\phantom{\rlap{--}f(n\!-\!1)}}\frac{f(n)}{\color{brown}{\rlap{---}f(n\!-\!1)}}\, =\  \frac{f(n)}{1} $
You can find many further examples of multiplicative telescopy in other posts here.
