Results 1 to 2 of 2

Math Help - induction by absurd

  1. #1
    Junior Member
    Joined
    Jan 2006
    Posts
    56

    induction by absurd

    here is a multipurpose pedagogic <<riddle>>

    Proove That (P(1) and( P(n)=>P(n+1) for n<=1))=>(P(n) for all n natural integer)

    Using this axiomatic property of N : Every subset of N admit a smallest element. (an element that belong to the subset and smaller than every element of the subset).

    This is very trivial i know but this property can be used in many demonstration( x^3+y^3=z^3 as no integer solution by Fermat for exemple)

    wont give the anwser!
    By!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by SkyWatcher
    here is a multipurpose pedagogic <<riddle>>

    Proove That (P(1) and( P(n)=>P(n+1) for n<=1))=>(P(n) for all n natural integer)

    Using this axiomatic property of N : Every subset of N admit a smallest element. (an element that belong to the subset and smaller than every element of the subset).

    This is very trivial i know but this property can be used in many demonstration( x^3+y^3=z^3 as no integer solution by Fermat for exemple)

    wont give the anwser!
    By!
    Suppose P(1) is true, and that P(n) \Rightarrow P(n+1).

    Let S \subset \mathbb{N} be the subset of \mathbb{N} for which P(n) is false.
    Then by the axiom there is a smallest element s of S,
    and s>1 by assumption.

    Then P(s-1) is true and P(s) is false, which is
    a contradiction of the assumption that P(n) \Rightarrow P(n+1).

    Hence there is no such element s and so there is no such
    set S. And so P(n)is true for every n \epsilon \mathbb{N}.

    (Note here we are taking \mathbb{N}=\{ 1,2,..\} if we want to
    use \mathbb{N}=\{ 0,1,2,..\}, we would have to start with P(0)
    being true rather than P(1) in our base case.)

    QED.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Induction?
    Posted in the Calculus Forum
    Replies: 0
    Last Post: June 6th 2009, 10:16 AM
  5. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM

Search Tags


/mathhelpforum @mathhelpforum