Prove by induction that $n^3 < 3^n$

Question

The question is prove by induction that $n^3 < 3^n$ for all $n\ge4$.

The way I have been presented a solution is to consider:

$$\frac{(d+1)^3}{d^3} = (1 + \frac{1}{d})^3 \ge (1.25)^3 = (\frac{5}{4})^3 = \frac{125}{64} <2 < 3$$

Then using this $$(d+1)^3 = d^3 \times \frac{(d+1)^3}{d^3} < 3d^3 < 3 \times 3^d = 3^{d+1}$$ so we have shown the inductive step and hence skipping all the easy parts the above statement is true by induction.

However I don't find this method very intuitive or natural; is there another way to attack this problem?

The approach I wish to take involves starting from $$ 3^{d+1} = 3 \times3^d > 3d^3$$ but then I do not know how show further that $3d^3 > (d+1)^3 $ to complete the inductive step. I have looked around at the proofs related to showing that $2^n > n^2 $ inductively for $n \ge 5$ but cannot relate the proof for that case to this case.

Also, is there a more general method that could be used to solve, say $a^n > n^a $ for $ n \ge k $ for some $k\in \Bbb R$

Answer 1

You need to show that

$$n^3<3^n\implies (n+1)^3<3^{n+1}$$

which amounts to

$$n^3<3^n\implies n^3<3\left(\frac n{n+1}\right)^33^n.$$

As $3\left(4/5\right)^3>1$ and the ratio is growing, the claim holds.

Answer 2

This base case holds because $4^3 < 3^4$.

To show that the inductive step holds, we need to show that:

$(n + 1)^3 < 3^{n + 1}$ holds if $n^3 < 3^n$ holds.

Note that:

$3^{n + 1} = 3 * 3^n > 3n^3$(since $3^n > n^3$ by the inductive hypothesis) > $(n + 1)^3$.

---

By binomial expansion: $(n + 1)^3 = n^3 + 3n^2 + 3n + 1$.

So:

$3n^3 ≥ (n + 1)^3\Leftrightarrow 3n^3 ≥ n^3 + 3n^2 + 3n + 1 \Leftrightarrow 2n^3 - 3n^2 - 3n - 1 ≥ 0. $

Since $2n^3 - 3n^2 - 3n - 1 = 0$ has a real solution at about $n \approx 2.26$ and $f(3) > 0$, we see that $2n^3 - 3n^2 - 3n - 1 > 0$ holds on the interval $(2.26,\infty)$. Then, because $4^3 < 3^4$, we see that:

$$3^{n + 1} > (n + 1)^3$$ for all $n \geq 4$, which is what we wanted to show.

---

Hope it helps.

Answer 3

First, show that this is true for $n=4$:

$4^3<3^4$

Second, assume that this is true for $n$:

$n^3<3^n$

Third, prove that this is true for $n+1$:

$(n+1)^3<$

$(n+\frac14n)^3=$

$(\frac54n)^3=$

$\frac{125}{64}n^3<$

$\frac{128}{64}n^3=$

$2\color\red{n^3}<$

$2(\color\red{3^n})<$

$3(3^n)=$

$3^{n+1}$

---

Please note that the assumption is used only in the part marked red.

Answer 4

The best solution that I can produce using some of the ideas from above is:

Proving the base case :

For $n=4$, we have $P(4): 3^4 > 4^3 \Leftrightarrow 81 > 64$ which is true.

Assume that the inequality is true for some d:

Assume $P(d): 3^d > d^3$.

Then show that $P(d+1)$ is true:

$P(d+1): 3^{d+1} > (d+1)^3 $

Starting from the RHS, $$(d+1)^3 = d^3 + 3d^2 + 3d +1 < 3^d + 3d^2 + 3d +1 $$ (using our inductive hypothesis)

Now if we can prove $3d^2 + 3d +1 < 3^d$ then we will be done.

So attempting to do this using induction again;

First if we prove that $6n+6 < 3^n$, we will be able to use this result later.

Proving the base case:

For $n=4$, $$6(4)+6 <3^4 \Leftrightarrow 30 < 81 $$ which is true.

Assume that the inequality is true for some j:

Assume $P(j): 6j+6 <3^j$

Then show that $P(j+1)$ is true:

$P(j+1): 6(j+1) +6 = 6j +6 +6 < 3^j+6 < 2(3^j) <3^{j+1}$

as $j \ge 4$ so 3^j > 6 for all j.

Thus, $6n+6 < 3^n$ is true for all $n \ge 4$.

Next, proving the base case for $3n^2 + 3n +1 < 3^n$:

For $n=4$, $$3(4^2) +3(4)+1 <3^4 \Leftrightarrow 61 < 81 $$ which is true.

Assume that the inequality is true for some k:

Assume $P(k): 3k^2 +3k +1 <3^k$

Then show that $P(k+1)$ is true:

$$P(k+1): 3(k+1)^2 +3(k+1) +1 = 3k^2 +3k +1 +(6k+6) < 3^k + 6k+6 < 2(3^k) <3^{k+1}$$

Therefore $3n^2 + 3n +1 < 3^n$ is true for all $n \ge 4$.

Going back to the question now,

$(d+1)^3 <3^d + 3d^2 +3d+1 <3^d +3^d <3^{d+1}$

So $3^n < n^3 $ for all $n \ge 4$ by mathematical induction! Although the working out for this approach is very long winded I find that it is more logical to a beginner at induction.