1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $$\frac{4(n+1)!}{4n!}=(n+1)>3=\frac{3^{n+1}}{3^n}.$$ $\endgroup$ – Jack D'Aurizio Jul 25 '16 at 22:56
  • $\begingroup$ You want $12n!\le 4(n+1)!$, not the converse! $\endgroup$ – egreg Jul 25 '16 at 22:58
  • $\begingroup$ $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. $\endgroup$ – JMoravitz Jul 25 '16 at 22:59
3
$\begingroup$

HINT By hypothesis, $n+1>3$

$\endgroup$
2
$\begingroup$

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}

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.