Results 1 to 3 of 3

Thread: 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 $\displaystyle n$, let $\displaystyle P(n)$ be a statement. If

    (1) $\displaystyle P(1)$ is true and
    (2) the implication

    If $\displaystyle P(k)$, then $\displaystyle P(k+1)$

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

    Proof:

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

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

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

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

  2. #2
    MHF Contributor

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

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

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

    And $\displaystyle s-1$ is the first integer less than $\displaystyle 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 $\displaystyle 1 {\color{blue}\notin} S$

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

    Yes, it's supposed to be $\displaystyle 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: Apr 9th 2011, 12:48 AM
  2. Problem understanding the theorem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Jan 5th 2010, 07:30 PM
  3. Help understanding this theorem/proof
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: Dec 8th 2009, 03:39 PM
  4. Need help understanding the Chinese Remainder Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 20th 2009, 11:55 AM
  5. Need help understanding the Chinese Remainder Theorem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Nov 18th 2009, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum