Prove the inequality by induction: $3^n > n^3$ for $n\ge4$

Question

Prove the inequality by induction:

$3^n > n^3\ $ for $\ n \geq 4$

Edit:

1) Base case: $n=4$, $3^4>4^3, 81>64$
2) Assume true for n=k: so $3^k>k^3$
3) Consider $(k+1)^3$, $(k+1)^3 = k^3 + 3k^2 +3k + 1 < k^3 + k^3 + k^3$, i.e. $(k+1)^3 < 3k^3$

For $k \geq 1$, $3(3^k) \geq 3(k^3)$, therefore $\ 3^{k+1}>3k^3>(k+1)^3$

And nowhere has the fact that $k \geq 4$ been used.., so I don't think this a complete, or at all a proof by induction of that inequality

The down-votes are probably because we value showing your work more than showing an answer. — The Chaz 2.0, Jul 13 '15 at 19:56
$k\ge4$ is used in your base case. Instead, try comparing $3^k$ and $k^3$ for $k=3$. — peterwhy, Jul 13 '15 at 20:05
@isquared-KeepitReal So the inequality is false for $k=3$. This is where the condition $k\ge4$ is necessary. — peterwhy, Jul 13 '15 at 20:09
"And nowhere has the fact that k≥4 been used" The condition $k\geqslant4$ is used to check the base case $k=4$. Note also that $k^3 + 3k^2 +3k + 1 < k^3 + k^3 + k^3$ requires $k\geqslant3$. — Did, Jul 13 '15 at 22:21

score 4 · Accepted Answer · answered Jul 13 '15 at 20:50

4

For the inductive step, we can massage the terms until it works: \begin{align*} (k + 1)^3 &= k^3 + 3k^2 + 3k + 1 \\ &< k^3 + 3k^2 + 3k + (k) &\text{since } k \geq 4 > 1 \\ &= k^3 + 3k^2 + 4k \\ &\leq k^3 + 3k^2 + (k)k &\text{since } k \geq 4 \\ &= k^3 + 4k^2 \\ &\leq k^3 + (k)k^2 &\text{since } k \geq 4 \\ &= 2k^3 \\ &< 3k^3 \\ &< 3(3^k) &\text{by the induction hypothesis} \\ &= 3^{k + 1} \end{align*} as desired.

answered Jul 13 '15 at 20:50

Adriano

41,576

1

Very nice! I like it! Thank you – Naz Jul 13 '15 at 20:52

score 0 · Answer 2 · answered Jul 13 '15 at 20:03

0

First, verify the statement for the base case, $n=4$: $$3^4 = 81 > 4^3 = 64$$ Now, assume it is true for $n$: $$3^n > n^3$$

All you have to do now is make it true for $n+1$: $$(n+1)^3 = n^3 + 3n^2 + 3n + 1 < 3^n + 3n^2 + 3n + 1 < 3^n + 2(3)^n = 3^{n+1}$$

Can you see why $3n^2 + 3n + 1 < 2(3)^n$ is true $\forall n \geq4 $ ?

answered Jul 13 '15 at 20:03

Race Bannon

1,829

hmmm.. I can't see why $3n^2+3n+1<2(3)^n$, but it is actually even true for $n=3$ – Naz Jul 13 '15 at 20:17
Try to use induction! – Race Bannon Jul 13 '15 at 20:20
Ok, so it is true for $\ n \geq 3 $ – Naz Jul 13 '15 at 20:48
And then $\ 3^n(1+2) $ :) beautiful. Thank you :) – Naz Jul 13 '15 at 20:49

score 0 · Answer 3 · answered Jul 13 '15 at 21:08

Here is an alternate way to complete the induction step:

Assume that $3^n>n^3$ for some integer $n\ge4$.

Then $3^{n+1}=3(3^n)>3n^3$, and $3n^3>(n+1)^3$

since $\displaystyle\frac{(n+1)^3}{n^3}=\left(\frac{n+1}{n}\right)^3=\left(1+\frac{1}{n}\right)^3\le\left(1+\frac{1}{4}\right)^3=\frac{125}{64}<3$ for $n\ge4$;

so $3^{n+1}>(n+1)^3$.

Prove the inequality by induction: $3^n > n^3$ for $n\ge4$

3 Answers3