Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Can you make the induction step by contradiction?

  1. Jun 19, 2016 #1
    Assuming you've sufficiently proven your inductive basis, can you complete a proof by induction in the following manner:

    Make the inductive hypothesis, assume P(n) is true for some n. Assume P(n+1) is not true. If it follows from the assumption that P(n+1) is false that P(n) must also therefore be false, contradicting the inductive hypothesis, does this mean P(n) must imply P(n+1)?
     
  2. jcsd
  3. Jun 19, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that is valid.
    The assumption from which you derived the contradiction was ##\exists n\ P(n)\wedge\neg P(n+1)##. Deriving a contradiction from this proves its negation, which is ##\forall n\neg(P(n)\wedge \neg P(n+1))##
    which, by de Morgan, is equivalent to
    ##\forall n\ \neg P(n)\vee P(n+1)##
    which is equivalent to
    ##\forall n\ P(n)\to P(n+1)##
    which is what we need to complete the induction.
     
  4. Jun 19, 2016 #3
    Lovely, thank you :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Can you make the induction step by contradiction?
  1. Can you draw? (Replies: 11)

Loading...