# Proof By Mathematical Induction - Example Help

• Oct 16th 2007, 02:01 AM
name101
Proof By Mathematical Induction - Example Help
hello just started school 2 days ago. and we were told to copy down some examples and there was one were i think there is a mistake but not sure.

Use mathematical induction to prove
$\displaystyle 3^n >= 2n + 5$ for all integers

i understand all the steps untill it does this.

$\displaystyle 3^(k+1) >= 2(2k+5)$
$\displaystyle 3^(k+1) >= 6+15$
$\displaystyle 3^(k+1) >= 2k+7$ <This line i do not understand.
Therefore
$\displaystyle 3^(k+1) >= 2(k+1) + 5$ <This line i do not understand.

could some one prove this is true or false..
• Oct 16th 2007, 04:37 AM
topsquark
Quote:

Originally Posted by name101
hello just started school 2 days ago. and we were told to copy down some examples and there was one were i think there is a mistake but not sure.

Use mathematical induction to prove
$\displaystyle 3^n >= 2n + 5$ for all integers

i understand all the steps untill it does this.

$\displaystyle 3^(k+1) >= 2(2k+5)$
$\displaystyle 3^(k+1) >= 6+15$
$\displaystyle 3^(k+1) >= 2k+7$ <This line i do not understand.
Therefore
$\displaystyle 3^(k+1) >= 2(k+1) + 5$ <This line i do not understand.

could some one prove this is true or false..

There are two lines I don't understand here, and they aren't the ones you noted. I'm kinda lost on the first two.

Let me run through this one.

I presume you've already done the base case so I won't redo that.

We are assuming that, for some value of k:
$\displaystyle 3^k \geq 2k + 5$

We need to show that this is true for the k + 1 case. So consider
$\displaystyle 3^{k + 1} = 3 \cdot 3^k$

But we know that
$\displaystyle 3^k \geq 2k + 5$

So
$\displaystyle 3^{k + 1} = 3 \cdot 3^k \geq 3(2k + 5)$<-- (1)

Thus
$\displaystyle 3^{k + 1} \geq 6k + 15$ <-- (2)

We also know that
$\displaystyle 6k + 15 > 2(k + 1) + 5$ <-- This step is easy to show. I leave it to you.

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

The lines I have labeled as (1) and (2) are what I think your lines 1 and 2 are meant to have been.

-Dan
• Oct 16th 2007, 06:23 AM
Soroban
Hello, name101!

Quote:

Use mathematical induction to prove: .$\displaystyle 3^n \:\geq \:2n + 5$ for all integers
This is not true for all integers.
Could it have said: .for all $\displaystyle n \geq 2$ ?

Here's the way I would do the proof.
. . I suspect that "they" had the same idea.

Verify the base case. .$\displaystyle S(2)\!:\;\;3^2 \,\geq\,2\!\cdot2 + 5$ . . . True!

Assume $\displaystyle S(k)\!:\;\;3^k \:\geq\:2k + 5$

Multiply both side by 3:. $\displaystyle 3\cdot3^k \:\geq \:3(2k+5)$

. . and we have: .$\displaystyle 3^{k+1}\:\geq\:6k + 15$

Now we note that: .$\displaystyle 6k + 15 \;=\;2k + 4k + 2 + 5 + 8 \;=\;2k + 2 + 5 + 4k + 8$

. . . . . . . . . . . . $\displaystyle =\:2(k+1) + 5 + (4k+8) \;>\;2(k+1) + 5$ .
. . . since $\displaystyle k$ is positive

Therefore, we have: .$\displaystyle 3^{k+1} \:\geq \:2(k+1) + 5$
. . and the inductive proof is complete.

• Oct 16th 2007, 09:08 PM
name101
Quote:

Originally Posted by Soroban
[size=3]This is not true for all integers.
Could it have said: .for all $\displaystyle n \geq 2$ ?

Ahhh yes I should of mentioned that fact.

Quote:

Originally Posted by Soroban
Therefore, we have: .$\displaystyle 3^{k+1} \:\geq \:2(k+1) + 5$
. . and the inductive proof is complete.

Ahh thank you both. there were a couple of steps that were missing in the book.(I dont think it was a very good example to be learning off) but as i said.

Thankyou
and ill be back with more questions :D

~Regards
Name101
• Oct 17th 2007, 03:52 AM
topsquark
Quote:

Originally Posted by name101
(I dont think it was a very good example to be learning off)

I think it is an excellent example to be learning from, given the nature of the substitutions that need to be made to solve the problem. That and the fact that there are many ways to go about doing it.

-Dan
• Oct 19th 2007, 01:44 AM
name101
Quote:

Originally Posted by topsquark
I think it is an excellent example to be learning from, given the nature of the substitutions that need to be made to solve the problem. That and the fact that there are many ways to go about doing it.

-Dan

I have been doing some more questions on the topic. and I revoke that statement.