Prove that $2^n>n^4$ for all $n\geq 17$

Question

I'm always a bit fuzzy on how to solve induction problems involving inequalities. I've managed to get somewhere though, but it looks like I have to go down four levels of induction to prove.

This is what I have so far:

Base ($n=17$):

$$2^{17}>17^4\Rightarrow131072>83521$$

Step:

Assumption: $2^k>k^4$

\begin{align} 2^{k+1}&>(k+1)^4\\ 2\cdot 2^{k}&>(k+1)^4\\ 2^k+2^k&>k^4+4k^3+6k^2+4k+1 \end{align}

From here, it looks like I need to claim that $2^k+2^k>k^4+2^k$, but in order to do this, I would then need to prove that $2^k>4k^3+6k^2+4k+1$, and then again probably one or two more times.

Is there a different approach I can take other than going down this long and tedious route?

Answer 1

Since $k\ge17$, we have $k^3>k^2>k>1$. Therefore

$$k^4+4k^3+6k^3+4k^3+k^3>k^4+4k^3+6k^2+4k+1$$ $$k^4+15k^3>k^4+4k^3+6k^2+4k+1$$ $$k^4+k^4>k^4+15k^3$$

Now, using the assumption for the inductive step, we have

$$2^k+2^k>k^4+k^4>k^4+15k^3>k^4+4k^3+6k^2+4k+1$$

Answer 2

Since we have $k^4>4k^3+6k^2+4k+1$ for all $k\ge 6$ we have $$ 2^k>k^4>4k^3+6k^2+4k+1 $$ for all $k\ge 17$, and the induction step is finished. I do not find it tedious.

Answer 3

You almost did it. $$ 2^{k}>4k^3+6k^2+4^k+1 $$ You know $$ 2^{k}>k^4\text{ and } k > 17 $$ $$ k^4 = k.k^3 > 17k^3 = 4k^3 + 13k.k^2 = 4k^3 + 6k.k^2+7k.k^2> 4k^3 + 6k^2+7k.k^2 = 4k^3 + 6k^2+4k.k^2+3k.k^2> 4k^3 + 6k^2+7k.k^2 = 4k^3 + 6k^2+4k+1 $$ Therefore $$ 2^{k}>k^4 >4k^3 + 6k^2+4k+1 $$ Done!

Answer 4

all that is required for the induction step is $$ (n+1)^4 < 2 n^4 $$ for large enough $n,$ so
$$ \frac{(n+1)^4}{ 2 \, n^4} < 1. $$ This is the same as $$ \left( \frac{n+1}{n} \right)^4 = \left( 1 + \frac{1}{n} \right)^4 < 2 $$ This does not work for $n \leq 5,$ indeed $(6/5)^4 = 1296/ 625,$ but it does work for $n=6$ as $(7/6)^4 = 2401/1296$ and $2 \cdot 1296 = 2592.$ Meanwhile $$ = \left( 1 + \frac{1}{n} \right)^4 $$ is strictly decreasing in $n,$ so it is less than $2$ for all $n \geq 6.$ It may help to consider $n=10,$ as $(11/10)^4 = 14641/10000 = 1.4641 < 2.$

If $n \geq 17$ and $$ \frac{n^4}{2^n} < 1, $$ then also $n \geq 6,$ so when $n \geq 17,$ $$ \color{red}{\frac{(n+1)^4}{2^{n+1}} = \frac{n^4}{2^n} \cdot \frac{(n+1)^4}{2 n^4} < \frac{n^4}{2^n} < 1} $$

No real tricks here: if you have positive things $A,B$ that depend on some $n,$ and you want to show $A < B,$ you can try for $A-B < 0$ or for $\frac{A}{B} < 1.$ Either way might give you something simpler than separately considering $A,B.$ The induction step then becomes showing that the left hand side decreases as $n$ is increased to $n+1.$