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?
$\endgroup$ 64 Answers
$\begingroup$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.
$\endgroup$ 2 $\begingroup$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.
$\endgroup$ $\begingroup$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}$$
$\endgroup$ $\begingroup$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$.
$\endgroup$ 2
