Can we prove $3^n > n^3$ for all $n \geqslant 4$ using induction?

[SweatingBear]

We wish to show that $3^n > n^3 \, , \ \forall n \geqslant 4 $. Base case $n = 4$ yields

$3^4 = 81 > 4^3 = 64 $

Assume the inequality holds for $n = p $ i.e. $3^p > p^3$ for $p \geqslant 4$. Then

$3^{p+1} > 3p^3$

$p \geqslant 4$ implies $3p^3 \geq 192$, as well as $(p+1)^3 \geqslant 125$. Thus $3p^3 > (p+1)^3$ for $p \geqslant 4$ and we have

$3^{p+1} > 3p^3 > (p+1)^3$

which concludes the proof.

Feedback, forum?

 

[alyafey22]

$p \geqslant 4$ implies $3p^3 \geq 192$, as well as $(p+1)^3 \geqslant 125$. Thus $3p^3 > (p+1)^3$ for $p \geqslant 4$ and we have

One question :

if x>5 and y>2 then x>y ?

 

[SweatingBear]

One question :

if x>5 and y>2 then x>y ?

I was actually a bit uncertain about that. How else would one go about?

 

[alyafey22]

We need to prove that

$$3^{p+1}> (p+1)^3$$ assuming that $$3^p>p^3\,\,\,\, \forall p\geq 4$$

$$\tag{1} 3^{p+1}>3p^3\geq p^3+p^3$$

Lemma :

$$p^3-3p^2-3p-1 \geq 0$$

Take the derivative

$$3p^2-6p-3 =3(p^2-2p-1)=3(p^2-2p+1-2)=3(p-1)^2-6$$

The function is positive for $p=4$ and increases for $$p\geq 4$$ so the lemma is satisfied .

Hence we have

$$p^3 \geq 3p^2+3p+1 \,\,\,\,\forall p\geq 4$$

Using this in (1) we get

$$3^{p+1}>p^3+3p^2+3p+1=(p+1)^3 \,\,\,\square$$

 

[Deveno]

Here is how I would do this proof:

(inductive step only).

Suppose that [math]3^k > k^3, k > 3[/math].

Then:

[math]3^{k+1} = 3(3^k) > 3k^3[/math].

If we can show that:

[math]3k^3 > (k+1)^3[/math], we are done.

Equivalently, we must show that:

[math]3k^3 > k^3 + 3k^2 + 3k + 1[/math], so that:

[math]2k^3 - 3k^2 - 3k - 1 > 0[/math].

Note that [math]2k^3 - 3k^2 - 3k - 1 > 2k^3 - 3k^2 - 5k + 3[/math]

if [math]2k - 4 > 0[/math], that is if [math]k > 2[/math], which is true.

But [math]2k^2 - 3k^2 - 5k + 3 = (2k - 1)(k^2 - k - 3)[/math].

Now [math]2k - 1 > 0[/math] for any [math]k > 0[/math], so we are down to showing

[math]k^2 - k - 3 > 0[/math] whenever [math]k > 3[/math].

Since [math]k^2 - k > 3[/math] is the same as [math]k(k-1) > 3[/math], we have:

[math]k(k-1) > 3(2) = 6 > 3[/math].

Thus we conclude that [math]k^2 - k - 3 > 0[/math] and so:

[math]3^{k+1} = 3(3^k) > 3k^3 > (k+1)^3[/math].

With all due respect to Zaid, I wanted to give a purely algebraic proof.

 

[Evgeny.Makarov]

Equivalently, we must show that:

[math]3k^3 > k^3 + 3k^2 + 3k + 1[/math]

Starting from this point, we could continue as follows. We need to show that $3k^2+3k+1<2k^3$.

$3k^2+3k+1<3k^2+3k^2+k^2=7k^2$ since $k>1$. Now, $7k^2<2k^3\iff 7<2k$, and the last inequality is true since $k\ge4$.

 

[Deveno]

Indeed, we just need to find something that is less than [math]2k^3[/math] and larger than [math]3k^2 + 3k + 1[/math] that "factors nice" (so we can apply what we know specifically about [math]k[/math]). Very nice solution!