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!

Even and Odd Natural Numbers

  1. Jul 9, 2009 #1

    jgens

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    Prove that every Natural number is either even or odd.

    2. Relevant equations

    Mathematical Induction
    Even: n = 2k where k is an integer
    Odd: n = 2k + 1 where k is an integer

    3. The attempt at a solution

    I think I have a relatively complete proof, however, it doesn't seem quite right (perhaps it's incorrect?). So, any suggestions or comments would be very helpful.

    Proof: We define the terms even and odd as follows: A Natural number n is even if it satifies n = 2(j) where jZ. A Natural number n is odd if it satisfies n = 2(j) + 1 where jZ.

    Now, let P(x) be the statement that every Natural number is either even or odd. Clearly, we have that n = 1 is odd since if j = 0 then 2(0) + 1 = 1. Additionally, we also have that n = 2 is even since if j = 1 then 2(1) = 2. Now suppose that P(x) is false for some non-empty set of Natural numbers. Since this set is non-empty, by the well-ordering principle it contains a least element n = k + 1. Because 1 and 2 are odd and even respectively and because n = k + 1 is the smallest n such that P(x) is false, we know that P(k) must be true. Therefore, k must either be even or odd. We treat these cases separately.

    Case 1: Suppose that k is even, then for some jZ, k = 2(j). Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 1. However, this contradicts our assumption that k + 1 was neither even nor odd.

    Case 2: Suppose that k is odd, then for some jZ, k = 2(j) + 1. Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 2 = 2(j + 1). However, this contradicts our assumption that k + 1 was neither even nor odd.

    These contradictions prove that our assumption that n = k + 1 was the least n such that P(x) was false was incorrect. Therefore, the set of Natural numbers that are neither even nor odd must be empty and consequently, every Natural number is either even or odd.
     
    Last edited: Jul 10, 2009
  2. jcsd
  3. Jul 10, 2009 #2

    jgens

    User Avatar
    Gold Member

    Thinking back on it, I don't think that I need to prove that 2 is even. Here's the updated proof . . .

    Proof: We define the terms even and odd as follows: A Natural number n is even if it satifies n = 2(j) where jZ. A Natural number n is odd if it satisfies n = 2(j) + 1 where jZ.

    Now, let P(x) be the statement that every Natural number is either even or odd. Clearly, we have that 1 is odd since if j = 0 then 2(0) + 1 = 1. Hence P(1) is true. Now suppose that P(x) is false for some non-empty set of Natural numbers. Because this set is non-empty, by the well-ordering principle it contains a least element n = k + 1. Since 1 is odd and n = k + 1 is the smallest n such that P(x) is false, we know that P(k) must be true. Therefore, k must be either even or odd. We will treat these cases separately.

    Case 1: Suppose that k is even, then for some jZ, k = 2(j). Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 1. However, this contradicts our assumption that k + 1 was not odd.

    Case 2: Suppose that k is odd, then for some jZ, k = 2(j) + 1. Since the Natural numbers are inductive, if k is a Natural number, then k + 1 is also a Natural number. Therefore we have that k + 1 = 2(j) + 2 = 2(j + 1). However, this contradicts our assumption that k + 1 was not even.

    These contradictions prove that our assumption that P(x) was false for a non-empty set of Natural numbers was incorrect. Therefore, the set of Natural numbers that are neither even nor odd must be empty and consequently, every Natural number is either even or odd. Q.E.D.
     
  4. Jul 10, 2009 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    I presume you mean that P(x) is the statement that the natural number x is either even or odd. What you give here does not depend on "x" and P(1), P(2), etc. are all the same statement!

    That seems a lot more complicated than necessary. Having shown that P(1) is true, I had expected you to just use induction. Suppose P(m) is true. That is, m is either even or odd. Now it is easy to prove that P(m+ 1) is true, thus proving the general statement by induction.

    If P(m) is true, then m is either even or odd.

    case I: Suppose m is even: m= 2k for some integer m. Then m+ 1= ...

    case II: Suppose m is odd: m= 2k+1 for some integer m. Then m+ 1= ...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Even and Odd Natural Numbers
  1. Even or odd functions (Replies: 3)

  2. Odd or even function? (Replies: 7)

Loading...