# How can I prove that $2^n\ge n^4$?

I'm trying to prove the following inequality. $$2^n\ge n^4 (n>n_0)$$ I noticed that from $n = 20$, the following inequality holds, and I want to use induction for the proof. However I simply cannot find any way to prove whenever $n$ holds, $n+1$ also holds as well. Any help would be appreciated. Thanks!

• $2^{n+1} = 2\cdot2^n>2n^4$ by inductive hypothesis. You want that to be greater than or equal to $(n+1)^4$, so if you can show $2n^4\ge(n+1)^4$ you're done. Can you? By the way, welcome to the site! – Rick Decker Sep 26 '17 at 23:59
• Hint: show that $2n^4 \geq (n+1)^4\ \forall\ n \geq n_0$ by applying the binomial theorem on the RHS and using observation that $n \geq n_0 \implies n^4 \geq n_0 \times n^3$ and thus, distributing this $n_0$ cleverly across each of the terms of the binomial expansion except the $n^4$ term(How to handle this term?) – LastIronStar Sep 27 '17 at 0:01

You can use induction to show that $2^n \geq n^4$ for all $n \geq 16$. When $n = 16$, we have $2^{16} = 16^4$. Suppose that $2^n \geq n^4$ for $n \geq 16$. We will show that $2^{n+1} \geq (n+1)^4$: $$(n+1)^4 = \left(1 + \frac{1}{n}\right)^4 \cdot n^4 \leq \left(1 + \frac{1}{16}\right)^4 \cdot 2^n < 2 \cdot 2^n = 2^{n+1}.$$

$$2^n>n^4\iff 2^{n/4}>n.$$

Then

$$2^{n/4}>n\implies 2^{(n+1)/4}>\sqrt[4]2\,n>n+1$$ if $$n>\frac1{\sqrt[4]2-1}>5.$$

• @StellaBiderman The claim is only about the inductive step. You're right that you need to choose as base case some $n \geq 16$. – Yuval Filmus Sep 27 '17 at 15:30
• @StellaBiderman: no, I showed that the inductive step works as of $n=6$. But the base case requires higher $n$. – Yves Daoust Sep 27 '17 at 15:51
• @StellaBiderman: what is claimed is the implication, not a side or the other. But the true added value in my answer is that you can very easily get rid of the exponent $4$. – Yves Daoust Sep 27 '17 at 15:53

Because $$2^n=(1+1)^n>\binom{n}{9}>n^4$$ for all $n\geq20$.

Also, $$2^n>\binom{n}{5}>n^4$$ for all $n\geq130$.