# How to prove inequality $3^{n}≤4n!$ for $n≥4$ with mathematical induction?

Prove inequality $3^{n}≤4n!$ for $n≥4$ with mathematical induction.

Base step: $n=4$

$3^{4}≤4*4!$

$81≤96$, so statement is true.

Inductive step: We need to prove that this $3^{n+1}≤4(n+1)!$ is true.

To get left side we only need to multiply whole statement $3^{n}≤4n!$ with 3.

After that we get: $3^{n+1}≤12n!$

Now we want to show that $12n!>4(n+1)!$ ?

If my assumption is correct, how should i solve this inequality $12n!>4(n+1)!$ ?

• $$\frac{4(n+1)!}{4n!}=(n+1)>3=\frac{3^{n+1}}{3^n}.$$ – Jack D'Aurizio Jul 25 '16 at 22:56
• You want $12n!\le 4(n+1)!$, not the converse! – egreg Jul 25 '16 at 22:58
• $3^{n+1}=3\cdot 3^n \leq (n+1)\cdot 3^n$ since $n\geq 4$. Now apply induction hypothesis and make a comparison to replace $3^n$ and complete. – JMoravitz Jul 25 '16 at 22:59

HINT By hypothesis, $n+1>3$

Here is a sketch of the core induction argument--if you can understand each "why" in the margin, then the rest is a formality: \begin{align} 3^{k+1}&= 3\cdot3^k\\[1em] &\leq 3(4k!)\tag{why?}\\[1em] &< (k+1)(4k!)\tag{why?}\\[1em] &= 4(k+1)!\tag{why?} \end{align}

Hint  Equivalently we seek to prove that $\,f(n) = 4n!/3^n \ge 1\,$ for all $\,n\ge 4.$

Note $\,f(4)\ge1\,$ and $\,f(n\!+\!1)/f(n) = (n\!+\!1)/3 \ge 1\,$ for $\,n\ge 4\,$ so $\,\color{#c00}{f(n\!+\!1) \ge f(n)}\,$

Hence the induction reduces to a trivial one:  an $\rm\color{#c00}{increasing}$ sequence stays $\,\ge\,$ its initial value. From this view, the induction step becomes obvious, boiling down to transitivity of $\,\ge,\,$ i.e.

\begin{align} f(n)\ge f(4)\,&\Rightarrow\, \color{#c00}{f(n\!+\!1)\ge f(n)} \ge f(4)\\[0.3em] {\rm i.e.}\quad P(n)\,&\Rightarrow\,P(n\!+\!1)\end{align}

Remark  This is not an ad-hoc trick. Rather, it is a special case of a general method of transforming such problems into a simpler form where the inductive step is more obvious. It is a special case of multiplicative telescopy. Follow the link for many further examples.

Note that once you prove by induction that result about increasing sequences, you can invoke the result as a Lemma for other induction problems of this type (which are quite common, as you can see from the links).