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.
 A: 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$
A: 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
A: 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$$
A: 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.
