Results 1 to 8 of 8

Math Help - Mathematical Induction

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    7

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7
    Quote Originally Posted by mushroom View Post
    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?
    F \implies T is \displaystyle T (See Truth table.)

    This has nothing to do with induction, though.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,315
    Thanks
    1225
    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).

    To answer your other question, you can start with a false statement and get to a true one, but that won't help you prove anything using induction, because the base step won't work...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,315
    Thanks
    1225
    Quote Originally Posted by alexmahone View Post
    F \implies T is T (See Truth table.)

    This has nothing to do with induction, though.
    Actually, F -> T is T...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,274
    Thanks
    666
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,306
    Thanks
    1282
    Quote Originally Posted by Deveno View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,274
    Thanks
    666
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by mushroom View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum