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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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$