1. Limited time only! Sign up for a free 30min personal 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!

A little question about a proof

  1. Aug 2, 2013 #1
    1. The problem statement, all variables and given/known data

    Use math induction and cases to prove that every integer is even or odd.


    3. The attempt at a solution

    Let p(n): n is even or is odd.
    Let n be an integer. Assume p(n) is true.
    Then n is even or n is odd.

    Case 1: Assume n is even. Then n = 2k for some integer k. So n + 1 = 2k + 1. Thus n + 1 is odd.
    So, n + 1 is odd or n + 1 is even.
    Hence, p(n + 1) is true.
    Case 2: Assume n is odd.Then n = 2k + 1 for some integer k. So n + 1 = 2(k + 1). Thus n + 1 is even.
    So, n + 1 is even or n + 1 is odd.
    Hence, p(n + 1) is true.
    In either case, p(n + 1) is true. So, p(n) => p(n + 1)

    -------------------------------------------------------------

    I copied it from the back of my book. My question is how do we know n + 1 might also be even in Case 1 before we did Case 2? Is there a logical reason for that or is it just stylistic? I am inclined to re-write this proof like this below:



    ....

    Case 1: Assume n is even. Then n = 2k for some integer k. So n + 1 = 2k + 1. Thus n + 1 is odd.

    Hence, p(n + 1) is true

    Case 2: Assume n is odd.Then n = 2k + 1 for some integer k. So n + 1 = 2(k + 1). Thus n + 1 is even.

    Hence, p(n + 1) is true

    So, n + 1 is even or n + 1 is odd.

    In either case, p(n + 1) is true. So, p(n) => p(n + 1)

    ------------------------------------------------------

    I am reasoning like this:

    p or q

    Case 1: Assume p

    ....

    Therefore r

    Case 2: Assume q

    ....

    Therefore, s.

    Therefore r or s.

    ------------------------------------------
    Please, tell me where I am tripping up.

    Thanks.
     
    Last edited: Aug 2, 2013
  2. jcsd
  3. Aug 2, 2013 #2

    verty

    User Avatar
    Homework Helper

    It is a logical truth that A => A or B. The proof doesn't need it though, it is sufficiently obvious to be omitted.
     
  4. Aug 2, 2013 #3
    They are just being very precise in their proof. The statement p(n+1) means that n+1 is even or is odd. In Case 1, once you show that n+1 is odd, they want to make it extra clear that you have indeed shown that p(n+1) is true by explicitly stating it precisely: n+1 is even or is odd. Note that this is the actual exact statement of p(n+1). Then they follow it with: Hence, p(n+1) is true. They are not trying to say that p(n+1) might be even. They are including it though to match the structure of the original statement you are trying to prove. As verty stated, it is obvious enough so as to be omitted.

    Junaid Mansuri
     
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: A little question about a proof
  1. Question about proof (Replies: 7)

Loading...