$2^n > n^4$ proof by induction

Question

This is what I came up with so far:

Inductive step: assume $2^n > n^4$. Need to prove $2^{n+1} > (n+1)^4$ $$ 2^{n+1} = 2 \cdot 2^n > 2 \cdot n^4\\ (2 \cdot n^4)^{1/4} = (2)^{1/4} \cdot n > n+1 \implies 2n^4 > (n+1)^4 \implies 2^n > (n+1)^4 $$

Is there a better way to solve this problem?

Answer 1

As others have noted, your induction proof ultimately suffers from establishing what your base case is. Your deduction that $$ 2^{1/4}(n)>n+1 $$ requires $n\geq6$, as Barry notes, but your inequality is not even true until $n\geq17$, as lulu notes. This means that your base case should be, at minimum, for when $n=17$. Then you can proceed exactly as you have done.

---

"Is there a better way to solve this problem?" Sure: use the fact that any exponential function eventually overtakes any power function (with bases $>1$ of course). But that is not all that insightful here--perhaps you are after something more intuitive perhaps? If so, please specify.

Answer 2

Using the function $x^{1/4}$ is not a purely algebraic proof. Here is one. Explicitely, we'll prove $2^n>n^4$ for all $n>16$.

For that, we'll prove by induction that if $n\ge 16$ and $2^n\ge n^4$, then $2^{n+1}>(n+1)^4$.

For $n=16$, we have an equality: $2^{16}=16^4$.

Now suppose that, for some $n\ge 16$, we have $2^n>n^4$. Then $2^{n+1}=2\cdot 2^n\ge 2n^4$. So we have to prove $2n^4>(n+1)^4$, i.e. $$n^4>4n^3+6n^2+4n+1.$$ As $n>1$, $\;4n^3+6n^2+4n+1>4n^3+6n^3+4n^3+n^3=15n^3$.

So it is enough to prove $n^4>15n^3$, which is equivalent to $n>15$. We've supposed $n\ge 16$.

Answer 3

There is another inductive way, I don't know if better or worse:

Our goal is to prove that $2^{n+1}>(n+1)^4$, assuming that $2^n>n^4$ and, as noted, $n\ge 17$. Let's estimate $2^{n+1}-(n+1)^4$:

$$2^{n+1}-(n+1)^4=\big(2^n-[(n+1)^4-n^4]\big)+(2^n-n^4)>(2^n-n^4)+(2^n-n^4)>0$$

To show the first inequality we have to check: $$(n+1)^4-n^4<n^4$$ but

$$\left(\frac{n+1}n\right)^4\le\left(\frac{18}{17}\right)^4<2$$

Answer 4

Here is a nice little non-induction proof that $n^4\lt2^n$ for $n\gt16$.

Note that

$$n^4=\left(\sqrt n\over2\right)^8\cdot2^8\cdot1^{n-16}$$

So if $n\gt16$, the arithmetic-geometric mean inequality tells us

$$\sqrt[n]{n^4}\lt{8\cdot\left(\sqrt n\over2\right)+8\cdot2+(n-16)\cdot1\over n}={4\over\sqrt n}+1\lt2$$

hence $n^4\lt2^n$.

(Remark: for $n=16$ both inequalities in the displayed expression become equalities. In particular, all $16$ terms in the AGM product $\left(\sqrt4\over2\right)^8\cdot2^8$ are equal to $2$. For $n\lt16$, the AGM connection falls apart, as it must, since the inequality goes the other way.)