# Proving $\frac{n^n}{3^n} < n!$ for $n\ge6$ by induction

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.

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

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$

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

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

• 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 – CodeR Aug 26 '15 at 18:18
• @coder, as $a>b;b>c\implies a>c$ – lab bhattacharjee Aug 26 '15 at 18:21
• 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"... – Did Aug 26 '15 at 19:10
• @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 – CodeR Aug 26 '15 at 20:44

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

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

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.