Prove $3^n \ge n^3$ by induction

Question

Yep, prove $3^n \ge n^3$, $n \in \mathbb{N}$.

I can do this myself, but can't figure out any kind of "beautiful" way to do it.

The way I do it is:

Assume $3^n \ge n^3$

Now,

$(n+1)^3 = n^3 + 3n^2 + 3n + 1$,

and $\forall{} n \ge 3$,

$3n^2 \le n^3, \,\, 3n + 1 \le n^3$

Which finally gives $(n+1)^3 \le 3n^3 \le 3^{n+1}$ by our assumption.

Now just test by hand for n=1,2,3 and the rest follows by induction.

Anyone got anything simpler?

Answer 1

Show true for $n=1,2,3$, and assume true for $k$. Then note that $3^{k+1} = 3^{k}\cdot 3 \geq 3\cdot k^3 = (3^{1/3}\cdot k)^3$ (by our assumption). Now, for $k\geq 3$, we see that $3^{1/3}\cdot k \geq k+1$ and the result follows.

Answer 2

Basis:

$n = 1$

$$3^1 \ge 1^3 \implies 3 \ge 1\text{, which is true}$$

Inductive hypothesis

Let $n=k$ and also let this inequality hold:

$$3^k \ge k^3$$

Inductive step

We'll prove that it also holds when $n=k+1$

$$3^{k+1} \ge (k+1)^3$$ $$3^k \cdot 3 \ge k^3 + 3k^2 + 3k + 1$$ $$3^k + 3^k + 3^k \ge k^3 + 3k^2 + 3k + 1$$

Now obviously as $3^k \ge k^3$ by the inductive hypothesis it's enough to show that

$$2 \cdot 3^k \ge 3k^2 + 3k + 1$$

Note that for every $k \ge 2$, this inequality holds $3k^2 \ge 3k + 1$

$$2 \cdot 3^k \ge 6k^2$$ $$3^k \ge 3k^2$$

This is true for every $k \ge 3$

Now you can prove the other 2 cases $n = 1,2$ to give a complete proof.

Answer 3

I don't know about beauty, but after verifying the inequality for the first three cases, one can use the fact that $64\lt81$ to conclude that $3\log(1+{1\over3})\lt\log3$. By combining this with the induction hypothesis, it follows that for $n\ge3$,

$$\begin{align} 3\log(n+1) &= 3\log n + 3\log(1+{1\over n})\cr &\le 3\log n +3\log(1+{1\over3}) \cr &\lt n\log3+\log3\cr &=(n+1)\log3 \end{align}$$

Answer 4

Here is another argument, but it's not necessarily simpler than yours:

1) If $n=1$, $3^1=3\ge1=1^3$; if $n=2$, $3^2=9\ge8=2^3$; and if $n=3$, $3^3=3^3$.

2) Now assume that $3^n\ge n^3$ for some integer $n\ge3$.

Then $\displaystyle\frac{1}{n}\le\frac{1}{3}$, so $\displaystyle\frac{(n+1)^3}{n^3}=\big(1+\frac{1}{n}\big)^3\le\big(\frac{4}{3}\big)^3=\frac{64}{27}\le3$, so

$\;\;\;\;\;\;\;\;3^{n+1}=3(3^n)\ge3n^3\ge(n+1)^3$.