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

  • Thread starter Thread starter SweatingBear
  • Start date Start date
  • Tags Tags
    Induction Proof
AI Thread Summary
The discussion focuses on proving the inequality \(3^n > n^3\) for all \(n \geq 4\) using mathematical induction. The base case for \(n = 4\) is established, showing \(3^4 = 81 > 4^3 = 64\). The inductive step assumes the inequality holds for \(n = p\) and demonstrates that \(3^{p+1} > (p+1)^3\) by establishing \(3p^3 > (p+1)^3\) for \(p \geq 4\). Various algebraic manipulations and lemmas are discussed to support the proof, confirming that the inequality holds for all specified values of \(n\). The conclusion affirms that the proof is valid and complete.
SweatingBear
Messages
119
Reaction score
0
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?
 
Physics news on Phys.org
sweatingbear said:
$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 ?
 
ZaidAlyafey said:
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?
 
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$$
 
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.
 
Deveno said:
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$.
 
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!
 
Back
Top