How do you prove that $4^n > n^3$ for all positive integers $n$?

Question

Prove that $4^n > n^3$ for every positive integer $n$ using the Principle of Mathematical Induction.

I am well aware of how to use this proof technique. I first showed that P(1) is true: $4^1 > 1^3$. Then I made the assumption that $4^k > k^3$ for an arbitrary positive integer $k$. Thus the goal is to show that $4^{k+1} > (k+1)^3$. So I tried changing the expression to $4^k \times 4 > (k+1)^3$. This is where I am stuck.

Answer 1

Which is bigger, $4$ or $(\frac{k+1}{k})^3$?

$1.5^3=3.375$

Well, $4^{k+1}=4^k\cdot 4>k^3\cdot 4>k^3\cdot (\frac{k+1}{k})^3=(k+1)^3$. This is no longer a hint now.

Answer 2

You probably want to extend your base case to examine $n=2$ explicitly as well, and then consider that for $k\ge 2$, moving from $k^3$ to $(k+1)^3$ will involve multiplying by a number no bigger than $\left(\frac{3}{2}\right)^3 = \frac{27}{8}<4$

Answer 3

$4^{k+1}=4\cdot 4^k > 4\cdot k^3 > (k+1)^3$ since $$\left(\frac{k+1}{k}\right)^3=\left(1+\frac{1}{k}\right)^3\leq\left(1+\frac{1}{2}\right)^3=(1.5)^3=3.375<4$$ (See eccstarup's answer).

Answer 4

To see if $4^n>n^3$ for all $n>1$, first establish bench marks.

For $n=1$, we see that $4^1=4>1^3=1$ checks. For $n=2$, we see that $4^2=16>2^3=8$ checks.

Now, assume that the inequality is true for some $k>2$. Then, $4^k>k^3$. Let's test to see if $4^{k+1}>(k+1)^3$.

$4^{k+1}=4(4^k)>4(k^3)$

Now, compare $4(k^3)$ to $(k+1)^3$. This is equivalent to comparing $4$ to $(1+k^{-1})^3$. But for $k>2$, $(1+k^{-1})^3\le (\frac43)^3=\frac{64}{27}<4$! And that is that.

Answer 5

Note: Here is an easy way of going about it: Let $S(n)$ denote the proposition that $$ S(n) : 4^n > n^3 $$ for all $n\geq 1$. We have that $S(1)$ is true because $4^1=4>1=1^3$. Also, we have that $S(2)$ is true because $4^2=16>8=2^3$ (these are the base cases). Thus, let's prove $S(n)$ to be true for all $n\geq 2$ (the reason for this will become clear in a moment).

Inductive step: Fix some $k\geq 2$ and assume that $$ S(k) : 4^k > k^3 $$ holds. To be shown is that $$ S(k+1) : 4^{k+1} > (k+1)^3 $$ follows. Starting with the left-hand side of $S(k+1)$, \begin{align} 4^{k+1} &= 4\cdot 4^k\tag{by definition}\\[0.5em] &> 4\cdot k^3\tag{by $S(k)$}\\[0.5em] &> (k+1)^3,\tag{since $k\geq 2$; see $(\dagger)$ for reason} \end{align} we end up at the right-hand side of $S(k+1)$. This concludes the inductive step.

By mathematical induction, we see that $S(n)$ holds for all $n\geq 2$. Also, since the base case held for $n=1$, we know that $S(n)$ holds for all $n\geq 1$.

---

$(\dagger)$: Note that $$ (k+1)^3 = k^3+3k^2+3k+1, $$ and $$ 4k^3 > k^3+3k^2+3k+1 \Longleftrightarrow 3k^3-3k^2-3k>1 \Longleftrightarrow \underbrace{3k(k^2-k-1)>1}_{\text{true if $k\;\geq\;2$}}. $$ Does it make sense now?

Answer 6

In case you don't want to use induction:

I proved (using induction twice) that if $n$ and $k$ are integers and $k \ge 2$ and $n \ge k^2+1$, then $2^n > n^k$ here: Prove that $n^k < 2^n$ for all large enough $n$

Putting $k=2$, $n^2 < 2^n$ for $n \ge 5$, so, squaring, $4^n > n^4 > n^3$ for $n \ge 5$.

For completion, examine the smaller $n$.

Answer 7

Hint:-

Instead of proving the inequality directly apply induction to the statement that, $$P(k):\sqrt[3]{4}-1>\dfrac{1}{k}$$

---

If you are interested in other methods then,

• Let $u_n=\dfrac{4^n}{n^3}$. Then, $$\dfrac{u_{n+1}}{u_n}=\dfrac{4}{\left(1+\dfrac{1}{n}\right)^3}$$Now note that $n\ge\left\lceil\dfrac{1}{\sqrt[3]{4}-1}\right\rceil\implies 4>\left(1+\dfrac{1}{n}\right)^3$.

• Alternatively you can examine the behavior of the function $f(x)=4^x-x^3$ and note that since $f$ is increasing it is sufficient to find the value of $x$ at which $f>0$.