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

Question

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)!$ ?

Answer 1

HINT By hypothesis, $n+1>3$

Answer 2

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}

Answer 3

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).