Proving $4^n > n^4$ holds for $n\geq 5$ via induction.

Question

I know that it holds for $n=5$, so the first step is done.

For the second step, my IH is: $4^n > n^4$, and I must show that $4^{n+1} > (n+1)^4$. I did as follows:

$4^{n+1} = 4*4^n > 4n^4$, and if I show that $4n^4 > (n+1)^4$ holds for $n\geq 5$ I'm done, so I expand the right hand side and arrive to:

$$4n^4 > n^4 + 4n^3 + 6n^2 + 4n + 1$$

And this holds iff: $$3n^4 - 4n^3 - 6n^2 - 4n - 1 >0$$ And here I'm stuck, I don't really know how to show that the given inequality holds. Any hints?

Answer 1

We only need to show that $4\ge (\frac{n+1}{n})^4=(1+\frac{1}{n})^4$ for $n\ge 5$ to prove the induction step, and this only need be shown for $n=5$ because as $n$ increases, $(1+\frac{1}{n})^4$ decreases.

Answer 2

Well you are not far... $$ 3n^4-4n^3-6n^2-4n-1=(n^2-2n-1)(3n^2+2n+1) $$ and that is always greater than zero for $n\ge 3$ (easy to see). The second term is always greater than zero since n is positive, and the first one is always greater than zero for $n\ge 3$.

Make sense?

Umberto

Answer 3

Another way to show that $3n^4>4n^3+6n^2+4n+1$ for $n\ge5$ is to use

$3n^4\ge15n^3=4n^3+11n^3\ge4n^3+55n^2=4n^3+6n^2+49n^2\ge4n^3+6n^2+245n$

$\;\;\;\;\;\ge4n^3+6n^2+4n+1$ for $n\ge5$ (although I prefer Will Hunting's approach).

Answer 4

You could also split the inequality into 3 pieces:

$n^4 > 4n^3 \Longleftrightarrow n > 4$

$n^4 > 6n^2 \Longleftrightarrow n^2 > 6$

$n^4 > n+1 \Longleftrightarrow n^3 > 1/n$

You can easily see that the inequalities are all true, because $n$ is at least equal to $5$.