1
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Another textbook question I'm stuck on says use induction to prove that for any complex number z (is not equal to) 1, and integer n(greather than or equal to) 1 , (1+z+z^2+z^3+..z^n)={1-z^(n+1)]/(z-1) $\endgroup$ – user212261 Feb 18 '15 at 21:44
  • $\begingroup$ @user212261 You mean $(1+z+z^2+\cdots+z^n)=\frac{z^{n+1}-1}{z-1}$. Observe that $\frac{z^n-1}{z-1}+z^{n}=\frac{z^{n+1}-1}{z-1}$ and clearly for $n=1$ we have that $1+z=\frac{z^2-1}{z-1}$ holds. $\endgroup$ – user26486 Feb 18 '15 at 21:52
  • $\begingroup$ yeah that seems correct the only thing is in the textbook the right hand side is 1-z^(n+1) in the numerator not the other way around but that should be equivalent $\endgroup$ – user212261 Feb 18 '15 at 21:54
  • 1
    $\begingroup$ @user212261: It is better if you can post this as a question with your work by highlighting where you stuck. Just posting the question is like asking others to do your work. $\endgroup$ – Extremal Feb 18 '15 at 21:55
  • 2
    $\begingroup$ @user212261 please ask this as a separate question. Do not use comments to ask questions! $\endgroup$ – Mariano Suárez-Álvarez Feb 18 '15 at 21:57
5
$\begingroup$

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}.$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.