3
$\begingroup$

How would I prove this using mathematical induction: $\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$.

Here is what I have tried:

$\dfrac{n^n}{3^n} < n!$ for all $n \geq 6$

Base case: $\dfrac{6^6}{3^6} < 6!$. Yes, this is true.

Assume for $k$ it's true so $\dfrac{k^k}{3^k} < k!$.

Now prove for $n=k+1$, $\dfrac{(k+1)^{k+1}}{3^{k+1}} < (k+1)!$.

By assumption, we have that $\dfrac{k^k}{3^k} < k!$.

Multiplying by $k+1$, we get $$ \frac{k^k(k+1)}{3^k} < (k+1) k! $$ and then $$ \frac{k^k(k+1)}{3^k} < (k+1) !. $$

I tried lots of things after this, but I am unable to figure out the proof.

$\endgroup$
  • $\begingroup$ Hint: start with $ \frac {(k+1)^{k+1}} {3^{k+1}} $! $\endgroup$ – Arpit Kansal Aug 26 '15 at 16:41
  • $\begingroup$ You multiplied by k+1 but forgot to divide by 3. $\endgroup$ – marty cohen Aug 26 '15 at 17:23
  • $\begingroup$ why are we starting with $n>=6$? $n>0$ works. $\endgroup$ – JMP Aug 26 '15 at 17:27
2
$\begingroup$

First recall the famous limit formula for the constant $e$:

$$\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n=e\approx 2.7182 \ldots<3.\tag{1}$$

Now recall the binomial theorem:

Binomial theorem: $$(x+y)^n=\sum_{i=0}^n\binom{n}{i}x^{i}y^{n-i}.\tag{2}$$

We may use $(2)$ (with $x=1/k$, $y=1$, and $n=k+1$) to rewrite $\sum_{i=0}^{k+1}\binom{k+1}{i}k^{1-i}$ in the following manner (rewriting this sum is necessary later on in the induction proof): \begin{align} \sum_{i=0}^{k+1}\binom{k+1}{i}k^{1-i}&= \sum_{i=0}^{k+1}\binom{k+1}{i}(1/k)^ik\tag{$k^{1-i}=(1/k)^ik$}\\[1em] &= k\sum_{i=0}^{k+1}\binom{k+1}{i}(1/k)^i\tag{pull out constant $k$}\\[1em] &= k\left(\frac{1}{k}+1\right)^{k+1}\tag{by $(2)$}\\[1em] &= k\left(\frac{1}{k}+1\right)\left(\frac{1}{k}+1\right)^k\tag{manipulate}\\[1em] &= \left(1+\frac{1}{k}\right)^k(k+1).\tag{simplify} \end{align} Hence, we have that $$ \sum_{i=0}^{k+1}\binom{k+1}{i}k^{1-i}=\left(1+\frac{1}{k}\right)^k(k+1).\tag{3} $$

With this in mind, see if you can follow the proof below by induction.


Claim: $\frac{n^n}{3^n}<n!$ for all $n\geq 6$.

Proof. For any integer $n$, let $S(n)$ denote the statement $$ S(n) : n^n<3^nn!. $$ Base case ($n=6$): $S(6)$ says that $46656=6^6<3^66!=524880$, and this is true.

Inductive step $S(k)\to S(k+1)$: Fix some $k\geq 6$. Assume that $$ S(k) : \color{blue}{k^k<3^kk!} $$ holds. To be shown is that $$ S(k+1) : \color{green}{(k+1)^{k+1}<3^{k+1}(k+1)!} $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} \color{green}{(k+1)^{k+1}}&= \sum_{i=0}^{k+1}\binom{k+1}{i}k^{k+1-i}\tag{by $(2)$}\\[1em] &= \color{blue}{k^k}\left(\sum_{i=0}^{k+1}\binom{k+1}{i}k^{1-i}\right)\tag{factor out $k^k$}\\[1em] &\color{blue}{<} \color{blue}{3^kk!}\left(\sum_{i=0}^{k+1}\binom{k+1}{i}k^{1-i}\right)\tag{by $S(k)$}\\[1em] &= 3^kk!\left(1+\frac{1}{k}\right)^k(k+1)\tag{by $(3)$}\\[1em] &< 3^kk![3(k+1)]\tag{by $(1)$}\\[1em] &= \color{green}{3^{k+1}(k+1)!},\tag{by definition(s)} \end{align} one arrives at the right-hand side of $S(k+1)$, completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 6$. $\blacksquare$

$\endgroup$
  • $\begingroup$ W Farlow : Great explaination thanks !! Is there any other way of proving the same using induction (any other simpler way) $\endgroup$ – CodeR Aug 27 '15 at 1:25
  • $\begingroup$ @CodeR I'm not sure what you mean exactly. Could you clarify? $\endgroup$ – Daniel W. Farlow Aug 27 '15 at 1:28
  • $\begingroup$ (You might want to mention that you're using that $(1+\frac{1}{n})^n$ increases to $e$.) $\endgroup$ – user84413 Aug 27 '15 at 19:39
0
$\begingroup$

HINT:

If $m!>\dfrac{m^m}{3^m}$

$\implies(m+1)!>m\cdot\dfrac{m^m}{3^m}$

It is sufficient to show $m\cdot\dfrac{m^m}{3^m}>\dfrac{(m+1)^{m+1}}{3^{m+1}}$

$\iff3>\left(1+\dfrac1m\right)^{m+1}$

Now $\left(1+\dfrac1m\right)^{m+1}>\left(1+\dfrac1{m+1}\right)^{m+1}$

Now see How is $a_n=(1+1/n)^n$ monotonically increasing and bounded by $3$? and An inequality $\,\, (1+1/n)^n<3-1/n \,$using mathematical induction

$\endgroup$
  • $\begingroup$ Can you please explain why proving m.m^m/3^m > (m+1)^m+1/3^m+1 is sufficient ? I am not from strong math background. Thank You for your reply $\endgroup$ – CodeR Aug 26 '15 at 18:18
  • $\begingroup$ @coder, as $a>b;b>c\implies a>c$ $\endgroup$ – lab bhattacharjee Aug 26 '15 at 18:21
  • 1
    $\begingroup$ The reduction to $3>\left(1+\frac1m\right)^{m+1}$ is suboptimal, this inequality fails for some small values of $m$, and the argument using $\left(1+\frac1m\right)^{m+1}>\left(1+\frac1{m+1}\right)^{m+1}$ is squarely wrong. Not sure I am very fond of such a "HINT"... $\endgroup$ – Did Aug 26 '15 at 19:10
  • $\begingroup$ @labbhattacharjee Ya i got that , but how do you get m*m^m/3^m after multiplying m^m/3^m by m+1 ? Thanks $\endgroup$ – CodeR Aug 26 '15 at 20:44
0
$\begingroup$

we have to show that $$(n+1)!>\frac{(n+1)^{n+1}}{3^{n+1}}$$ multiplying $$n!>\frac{n^n}{3^n}$$ by $$n+1$$ we get $$(n+1)!>\frac{n^n(n+1)}{3^n}$$ this must be greater as $$\frac{(n+1)^{n+1}}{3^{n+1}}$$ this is true since $$\left(1+\frac{1}{n}\right)^n<3$$

$\endgroup$
  • $\begingroup$ Dr Sonnhard can you please explain why it must be greater ? Thanks $\endgroup$ – CodeR Aug 26 '15 at 20:48
0
$\begingroup$

We will use induction to show that $\;\;\color{red}{3^n n!>n^n}$ for all $\color{blue}{n\ge1}$:

1) This is true for $n=1$, since $3>1$.

2) Let $n\in\mathbb{N}$ with $3^n n!>n^n$. Then $3^{n+1}(n+1)!=3(n+1)\big(3^n n!\big)>3(n+1)\big(n^n\big)$,

$\;\;\;$and $3(n+1)(n^n)>(n+1)^{n+1}\iff3n^n>(n+1)^{n}\iff3>\big(1+\frac{1}{n}\big)^n,\;$ and

$\hspace{.25 in}(1+\frac{1}{n})^n=\sum_{k=0}^{n}\binom{n}{k}(\frac{1}{n})^k=\sum_{k=0}^{n}\frac{n(n-1)(n-2)\cdots(n-(k-1))}{k!n^k}=\sum_{k=0}^{n}\frac{(1-\frac{1}{n})(1-\frac{2}{n})\cdots(1-\frac{k-1}{n})}{k!}$

$\hspace{.87 in}\le\sum_{k=0}^{n}\frac{1}{k!}=2+\sum_{k=2}^n\frac{1}{k!}\le2+\sum_{k=2}^n\frac{1}{k(k-1)}=2+\sum_{k=2}^n(\frac{1}{k-1}-\frac{1}{k})=3-\frac{1}{n}<3$

$\;\;\;$Therefore $3^{n+1}(n+1)!>(n+1)^{n+1}$.

Thus $\color{red}{3^n n!>n^n}$ for all $\color{blue}{n\ge1}$ by induction.

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