Results 1 to 3 of 3

Math Help - Need help understanding proof of theorem

  1. #1
    Banned
    Joined
    Sep 2009
    Posts
    502

    Need help understanding proof of theorem

    (The Principle of Mathematical Induction) For each positive integer n, let P(n) be a statement. If

    (1) P(1) is true and
    (2) the implication

    If P(k), then P(k+1)

    is true for ever positive integer k, then P(n) is true for every positive integer n.

    Proof:

    Assume, to the contrary, that the theorem is false. Then conditions (1) and (2) are satisfied but there exist some positive integers n for which P(n) is a false statement. Let

    S = \{n \in \mathbb{N}: P(n) is false \}

    Since S is a nonempty subset of \mathbb{N} , it follows by the Well-Ordering Principle that S contains s. Since P(1) is true, 1 \in S.
    Here I am lost:
    Thus s \geq 2 and s-1 \in \mathbb{N}. Therefore, s-1 \in S and so P(s-1) is a true statement. By condition (2), P(s) is also true
    and so s \not \in S. This however, contradicts our assumption that s \in S.

    Question: What is s-1?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,797
    Thanks
    1690
    Awards
    1
    Quote Originally Posted by novice View Post
    (The Principle of Mathematical Induction) For each positive integer n, let P(n) be a statement. If
    (1) P(1) is true and
    (2) the implication If P(k), then P(k+1)
    is true for ever positive integer k, then P(n) is true for every positive integer n.

    Proof:Assume, to the contrary, that the theorem is false. Then conditions (1) and (2) are satisfied but there exist some positive integers n for which P(n) is a false statement. Let
    S = \{n \in \mathbb{N}: P(n) is false \}
    Since S is a nonempty subset of \mathbb{N} , it follows by the Well-Ordering Principle that S contains s. Since P(1) is true, 1 \in S.
    Here I am lost:
    Thus s \geq 2 and s-1 \in \mathbb{N}. Therefore, s-1 \in S and so P(s-1) is a true statement. By condition (2), P(s) is also true
    and so s \not \in S. This however, contradicts our assumption that s \in S.
    Question: What is s-1?

    Above you must mean 1 {\color{blue}\notin} S

    And s-1 is the first integer less than s.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by Plato View Post
    [/b]
    Above you must mean 1 {\color{blue}\notin} S

    And s-1 is the first integer less than s.
    Thank you for the explanation. Now I understand.

    Yes, it's supposed to be 1\not \in S.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help understanding what this theorem means
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 9th 2011, 12:48 AM
  2. Problem understanding the theorem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: January 5th 2010, 07:30 PM
  3. Help understanding this theorem/proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: December 8th 2009, 03:39 PM
  4. Need help understanding the Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: November 20th 2009, 11:55 AM
  5. Need help understanding the Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 18th 2009, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum