1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is this a valid inductive proof?

Tags:
  1. Nov 26, 2016 #1
    Mentor note: moved to the homework section

    Claim: all numbers divisible by 4 are divisible by 2.

    Premise: let p(n) return 4n, I.e., the function covers all numbers divisible by four.

    Reasoning:

    Let n equal 1 in the base case

    P(n) is divisible by 2

    P(n+1) is divisible by 2

    By induction all n are divisible by 2

    QED
     
    Last edited by a moderator: Nov 26, 2016
  2. jcsd
  3. Nov 26, 2016 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I would say you have proved nothing.

    This should be homework.
     
  4. Nov 26, 2016 #3
    Can you find an inductive proof that all numbers divisible by 4 are divisible by 2?
     
  5. Nov 26, 2016 #4
    • (*) For all n, 4n%2=0

    • Let n = 1. Then:

      • 4n%2 = 0
      So (*) works for n = 1.

      Assume, for n = k, that (*) holds; that is, that

      4k%2
    • = 4%2 times k%2 by distributive property
    • = 0 times k%2
    • = 0

    • Let n = k + 1.

      • 4(k+1)%2
      • = (4k+4)%2 by distributive property
      • = 4k%2 + 4%2 by distributive property
      • = 4k%2 + 0
      • = 4k%2
      • = 4%2 times k%2 by distributive property
      • = 0 times k%2
      • = 0
      Then (*) works for n = k + 1.
     
    Last edited: Nov 26, 2016
  6. Nov 26, 2016 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That's better, but it's still short of a rigorous proof, if that's what you are trying to do.

    One problem is that your inductive step doesn't really use the inductive hypothesis.
    You can do this because the proof doesn't need induction.
     
  7. Nov 26, 2016 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Following the same logic, all numbers divisible by 4 are smaller than 10.
    Let n equal 1 in the base case.
    P(n) is smaller than 10
    P(n+1) is smaller than 10.
    By induction all numbers divisible by 4 are smaller than 10.

    This problem is not well suited for induction as the direct proof is much easier, even in the induction step.
    That's what you have to show.
     
  8. Nov 26, 2016 #7
    I know that, I just want to use an inductive proof. Can anyone find any for this problem or at least be specific?

    I edited the proof to show how 4k%2 = 0
     
    Last edited: Nov 26, 2016
  9. Nov 26, 2016 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Your approach in post #4 is good, especially after the recent edit.
    This step could get some more justification or a reference to something shown before.
    The last 3 steps don't make sense, but you don't need them. The first line is your assumption for the inductive step.
     
  10. Nov 26, 2016 #9

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You need to justify why ##4(k+1)## is divisible by 2. If you claim this is obvious, then there is no purpose to the proof, as this is entirely what you are trying to prove.
     
  11. Nov 26, 2016 #10
    I edited my post to include the distributive property. The tiny loops are not "0=", they are just artifacts.
     
  12. Nov 26, 2016 #11

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I think ##4(k+1) = 4k + 4 = 0 + 0 = 0 \mod 2## is simpler, where ##4k = 0 \mod 2## and ##4 = 0 \mod 2## follow from your inductive hypothesis and from the result for ##n =1##
     
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: Is this a valid inductive proof?
  1. Is my proof valid? (Replies: 5)

  2. Is this a valid proof? (Replies: 7)

  3. Induction Proof (Replies: 11)

Loading...