1. ## Mathematical Induction

I am still unclear about the principle of mathematical induction. For instance, let's say P(k) is false and P(k+1) is true, is the relationship "P(k) implies P(k+1)" true?

2. Originally Posted by mushroom
I am still unclear about the principle of mathematical induction. For instance, let's say P(k) is false and P(k+1) is true, is the relationship "P(k) implies P(k+1)" true?
$\displaystyle F \implies T$ is $\displaystyle \displaystyle T$ (See Truth table.)

This has nothing to do with induction, though.

3. Think of a string of dominoes. If you set up the dominos, pushing any one domino over should push over the next. But that of course is assuming you push the first domino over.

It works the same way with mathematical induction. You need to show that the base step P(1) is true (i.e. that you push the first domino over), and you need to show the inductive step, P(k) being true implying P(k+1) is true (i.e. that pushing any domino over pushes the next domino over).

4. Originally Posted by alexmahone
$\displaystyle F \implies T$ is $\displaystyle T$ (See Truth table.)

This has nothing to do with induction, though.
Actually, F -> T is T...

5. well, let's just try to prove that n < 2, for all natural numbers n, by induction:

1 < 2, ok, that works.

assume k < 2. without loss of generality, we may assume k > 1 (we have already proved that k=1 is true). but then this is false, so we may conclude truthfully that k < 2 implies k+1 < 2 is a true statement.

thus all natural numbers are less than 2. hum. what went wrong??

to see the problem, let P be our property (that we want to prove). suppose that P(a) is true for at least ONE natural number. induction is shorthand for the implication chain:

P(a)-->P(a+1)-->P(a+2)--->P(a+3)-->P(a+4)-->P(a+5)--->

if P is false for all natural numbers, we don't "get started". the base case is vital, we have to start with a true statement. chains of the form:

F-->T-->T-->T-->T-->... are not allowed.

but if we start with a true statement, and have a false statement somewhere "down the line":

T-->T-->T--->F-->T-->T-->T.....

then we can safely say that one of the statements: P(k)-->P(k+1) is false, which means that that for some k > a, P(k) is not true.

where did this happen in the proof above? right near the beginning: the weak link is: P(1)-->P(2). that "breaks the chain".

since 2 < 2 is false, we can abandon all hope of proving that all numbers greater than 1 are less than 2. this should be reassuring.

6. Originally Posted by Deveno
well, let's just try to prove that n < 2, for all natural numbers n, by induction:

1 < 2, ok, that works.

assume k < 2. without loss of generality, we may assume k > 1 (we have already proved that k=1 is true). but then this is false,
There's your error- having said "assume k< 2", you can't turn around and say it is false.

so we may conclude truthfully that k < 2 implies k+1 < 2 is a true statement.

thus all natural numbers are less than 2. hum. what went wrong??

to see the problem, let P be our property (that we want to prove). suppose that P(a) is true for at least ONE natural number. induction is shorthand for the implication chain:

P(a)-->P(a+1)-->P(a+2)--->P(a+3)-->P(a+4)-->P(a+5)--->

if P is false for all natural numbers, we don't "get started". the base case is vital, we have to start with a true statement. chains of the form:

F-->T-->T-->T-->T-->... are not allowed.

but if we start with a true statement, and have a false statement somewhere "down the line":

T-->T-->T--->F-->T-->T-->T.....

then we can safely say that one of the statements: P(k)-->P(k+1) is false, which means that that for some k > a, P(k) is not true.

where did this happen in the proof above? right near the beginning: the weak link is: P(1)-->P(2). that "breaks the chain".

since 2 < 2 is false, we can abandon all hope of proving that all numbers greater than 1 are less than 2. this should be reassuring.

7. well of course i made an error, i proved something untrue! it was deliberate.

a more subtle induction de-railment is this:

theorem: all horses have the same color.

P(1): if we have only one horse, of course it has the same color.

assume that for all k < n, all horses have the same color. now, if we have n horses, no matter which one we remove, all of the remaining n-1 horses must have the same color.

so if we remove horse A, the remaining n-1 horses have the same color, and if we add horse A, and remove another horse, B, we see that horse A and the n-2 horses remaining all have the same color, so A must have the same color as B, and the other n-2 horses. therefore n horses have all the same color.

thus every horse has that same color.

8. Originally Posted by mushroom
I am still unclear about the principle of mathematical induction. For instance, let's say P(k) is false and P(k+1) is true, is the relationship "P(k) implies P(k+1)" true?
Why would you want to have P(k) false ?
Do you want to prove that something is true or that something is false using induction ?

If you want to prove something is true for all positive natural numbers,
you show the following

True for 1 implies true for 2
True for 2 implies true for 3
True for 3 implies true for 4
True for 4 implies true for 5
and on and on and on.

You can do this IN GENERAL by showing that P(k) "being true" forces P(k+1) to be true too.
If that relationship exists, then the domino-effect runs through the proposition
as outlined by Prove It.
Then the first domino falls and knocks over all the others if P(1) is true.

If you want to show that something is false,
you may show that P(k) being false causes P(k+1) to also be false in turn.