# Proof critique: Induction

#### sweatingbear

##### Member
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?

#### ZaidAlyafey

##### Well-known member
MHB Math Helper
$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

##### Member
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?

#### ZaidAlyafey

##### Well-known member
MHB Math Helper
We need to prove that

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

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

Lemma :

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

Take the derivative

$$\displaystyle 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 $$\displaystyle p\geq 4$$ so the lemma is satisfied .

Hence we have

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

Using this in (1) we get

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

#### Deveno

##### Well-known member
MHB Math Scholar
Here is how I would do this proof:

(inductive step only).

Suppose that $$\displaystyle 3^k > k^3, k > 3$$.

Then:

$$\displaystyle 3^{k+1} = 3(3^k) > 3k^3$$.

If we can show that:

$$\displaystyle 3k^3 > (k+1)^3$$, we are done.

Equivalently, we must show that:

$$\displaystyle 3k^3 > k^3 + 3k^2 + 3k + 1$$, so that:

$$\displaystyle 2k^3 - 3k^2 - 3k - 1 > 0$$.

Note that $$\displaystyle 2k^3 - 3k^2 - 3k - 1 > 2k^3 - 3k^2 - 5k + 3$$

if $$\displaystyle 2k - 4 > 0$$, that is if $$\displaystyle k > 2$$, which is true.

But $$\displaystyle 2k^2 - 3k^2 - 5k + 3 = (2k - 1)(k^2 - k - 3)$$.

Now $$\displaystyle 2k - 1 > 0$$ for any $$\displaystyle k > 0$$, so we are down to showing

$$\displaystyle k^2 - k - 3 > 0$$ whenever $$\displaystyle k > 3$$.

Since $$\displaystyle k^2 - k > 3$$ is the same as $$\displaystyle k(k-1) > 3$$, we have:

$$\displaystyle k(k-1) > 3(2) = 6 > 3$$.

Thus we conclude that $$\displaystyle k^2 - k - 3 > 0$$ and so:

$$\displaystyle 3^{k+1} = 3(3^k) > 3k^3 > (k+1)^3$$.

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

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Equivalently, we must show that:

$$\displaystyle 3k^3 > k^3 + 3k^2 + 3k + 1$$
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

##### Well-known member
MHB Math Scholar
Indeed, we just need to find something that is less than $$\displaystyle 2k^3$$ and larger than $$\displaystyle 3k^2 + 3k + 1$$ that "factors nice" (so we can apply what we know specifically about $$\displaystyle k$$). Very nice solution!