Welcome to our community

Be a part of something great, join today!

Proof critique: Induction

sweatingbear

Member
May 3, 2013
91
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
Jan 17, 2013
1,667
$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
May 3, 2013
91

ZaidAlyafey

Well-known member
MHB Math Helper
Jan 17, 2013
1,667
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
Feb 15, 2012
1,967
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
Jan 30, 2012
2,492
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
Feb 15, 2012
1,967
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!