Results 1 to 6 of 6

Math Help - Proof Of Mathematical Induction

  1. #1
    Junior Member
    Joined
    Aug 2006
    Posts
    56

    Proof Of Mathematical Induction

    The manner in which mathematical induction is introduced in my textbook has me wondering about its proof:
    Theorem: The Principle of Mathematical Induction

    Suppose that the following two conditions are satisfied with regard to a statement about natural numbers:

    CONDITION I: The statement is true for the natural number 1.
    CONDITION II: If the statement is true for some natural number k, it is also true for the next natural number k + 1.

    Then the statement is true for all natural numbers.
    The text then goes on to say that this principle will not be proven, and then provides an analogy of falling dominos.

    What does the proof of this theorem look like?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    The proof of the validity of mathematical induction is by contradiction and depends upon the axiom of well ordering. That axiom states: Every subset of positive integers contain a first or a least integer. Using that axiom, suppose that the statement fails for some positive integer then it fails for sum first J. We know that J is not 1 because it is true for 1. Therefore, J-1 is positive integer and the statement is true for J-1 because J is the first for which it is not true. However if it is true for J-1 it must be true for (J-1)+1 =J. Thus there is a contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by spiritualfields View Post
    What does the proof of this theorem look like?
    The formal proof of this is based on Peano Axioms.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Aug 2006
    Posts
    56
    Thanks. It looks like the proof involves first supposing that the two conditions are true, then denying the second condition and using it to produce the contradiction of the condition being true and not true at the same time. After which there is the image of the mathematician in a tophat and tap shoes, clicking his heels with a flourishing "ta da!"
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by spiritualfields View Post
    Thanks. It looks like the proof involves first supposing that the two conditions are true, then denying the second condition and using it to produce the contradiction of the condition being true and not true at the same time. After which there is the image of the mathematician in a tophat and tap shoes, clicking his heels with a flourishing "ta da!"
    In at least some developments of arithmetic the principle of mathematical
    induction is an axiom.

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Aug 2006
    Posts
    56
    In at least some developments of arithmetic the principle of mathematical induction is an axiom.
    Yes, that's what I thought makes more sense after seeing the proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 24th 2011, 02:33 PM
  2. Proof by mathematical induction.
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: June 23rd 2011, 09:12 PM
  3. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 5th 2010, 11:24 AM
  4. Mathematical Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2010, 05:36 PM
  5. proof and mathematical induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 11th 2007, 11:16 AM

Search Tags


/mathhelpforum @mathhelpforum