Induction on powers

Question

If $n \geq 3$, prove that $3^n \geq n^3$.

Progress. I tried using induction and saying assume $3^k \geq k^3$. Then I got $3^{k+1} = 3^k \cdot 3 \geq 3k^3$. Now I am stuck.

Answer 1

So, we show the base case holds true (clearly since $3^3=3^3$).

So, we assume for our induction hypothesis that $3^k\geq k^3$ and wish to show it follows also for $k+1$ when $k\geq 3$.

(Keep in mind that because it isn't true for smaller values of $k$ that the fact that $k\geq 3$ will likely play a role somewhere in the proof)

We have:

$3^{k+1}=3\cdot 3^k \geq^{\text{I.H.}} 3\cdot k^3 = k^3+k^3+k^3$

$\geq k^3+3k^2+3k^2\geq k^3+3k^2+9k= k^3+3k^2+8k+k\geq k^3+3k^2+3k+1=(k+1)^3$

Where all inequalities on the second line are a result of $k\geq 3$ and the inequality on the first line is a result of the induction hypothesis.

With practice, one can recognize such inequalities with many fewer steps (I would personally have gone straight from $3k^3\geq (k+1)^3$).

Answer 2

First notice that

$$ 3^n \ge n^3 \;\; \Leftrightarrow \;\; n \ln{3} \ge 3 \ln{n} \;\; \Leftrightarrow \;\; \frac{\ln{3}}{3} \ge \frac{\ln{n}}{n}$$

then,

$$ \frac{d}{dn} \left( \frac{\ln{n}}{n} \right) = -\frac{\ln{n-1}}{n^2}$$

and since the right hand side is negative for $n\ge 3$ the result follows.

Answer 3

Now you want to argue that $3k^3 \gt (k+1)^3$ or $3 \gt (1+\frac 1k)^3$