# Thread: Problem with proof by mathematical induction

1. ## Problem with proof by mathematical induction

Hi,

I'm having trouble with this problem:

Use mathematical induction to show that:

$\displaystyle R_{n} : 5^n \geq n^5$ for all $\displaystyle n \geq 5.$

It suggests using this inequality as the basis for an approximation:

$\displaystyle (n+1)^5 = n^5 + 5n^4 + 10n^3 + (10n^2 + 5n + 1) < n^5 + n^5 + 2n^5 + n^5$

This is what I've done so far:

$\displaystyle (n+1)^5 = n^5 + 5n^4 + 10n^3 + (10n^2 + 5n + 1) < n^5 + n^5 + 2n^5 + n^5$

is equal to

$\displaystyle (n+1)^5 < 5n^5$

If

$\displaystyle 5^k \geq k^5$

then

$\displaystyle 5(5)^k \geq 5k^5$

which is equal to

$\displaystyle 5^{(k+1)} \geq 5k^5$

Since

$\displaystyle (n+1)^5 < 5n^5$

$\displaystyle 5^{(k+1)} \geq 5k^5 > (n+1)^5$

Therefore

$\displaystyle 5^{(k+1)} > (n+1)^5$

My problem is that I don't know how to get from

$\displaystyle 5^{(k+1)} > (n+1)^5$

to

$\displaystyle 5^{(k+1)} \geq (n+1)^5$

2. ## Re: Problem with proof by mathematical induction

Welcome to the forum.

First, we usually say "equal" referring to numbers and "equivalent" referring to propositions. This is because "equal" usually means "identical." In contrast, two propositions are equivalent if they imply each other, and they an be very different otherwise. There are even examples of equivalent propositions P and Q such that P is intuitively true and Q is intuitively false for many people (of course, their intuition is incorrect in this case).

Originally Posted by Electronegativity
Since

$\displaystyle (n+1)^5 < 5n^5$

$\displaystyle 5^{(k+1)} \geq 5k^5 > (n+1)^5$

Therefore

$\displaystyle 5^{(k+1)} > (n+1)^5$
As you said, you have $\displaystyle (n+1)^5 < 5n^5$ for any n >= 5. Since k >= 5 (this has to be stated as an assumption), instantiate n with k to get $\displaystyle (k+1)^5 < 5k^5$. Since $\displaystyle 5^{(k+1)} \geq 5k^5$, we have $\displaystyle 5^{(k+1)} \geq (k+1)^5$, which concludes the inductive step.

Don't forget the base case, when >= turns into =.