2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ $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! $\endgroup$ – Rick Decker Sep 26 '17 at 23:59
  • $\begingroup$ 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?) $\endgroup$ – LastIronStar Sep 27 '17 at 0:01
6
$\begingroup$

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}. $$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @StellaBiderman The claim is only about the inductive step. You're right that you need to choose as base case some $n \geq 16$. $\endgroup$ – Yuval Filmus Sep 27 '17 at 15:30
  • $\begingroup$ @StellaBiderman: no, I showed that the inductive step works as of $n=6$. But the base case requires higher $n$. $\endgroup$ – Yves Daoust Sep 27 '17 at 15:51
  • $\begingroup$ @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$. $\endgroup$ – Yves Daoust Sep 27 '17 at 15:53
-1
$\begingroup$

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

$\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.