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!

Discrete Mathematics: Proof problem for even integer

  1. Oct 31, 2011 #1
    1. The problem statement, all variables and given/known data

    For every non-negative integer z, z2 - 3z is an even integer. Prove this statement. So far, I have learned about direct proofs and indirect proofs such as contraposition and contradiction.

    2. Relevant equations

    An integer z is odd when there is an integer a so that z = 2a+1. An integer is even when there is an integer a such that z = 2a.

    3. The attempt at a solution

    I broke it down into to two parts where x is even and another where x is odd:

    For even, I substituted z = 2a into z2 - 3z to get (2a)2 - 3(2a). After expanding, I got 4a2 - 6a and further simplified it to get 2a(2a - 3).

    I tried using proof by contradiction by taking the negation of the statement and saying suppose there is at least one non-negative integer z, z2 - 3z is an odd integer.

    For odd, I substituted z = 2a + 1 to get (2a+1)2 - 3(2a + 1). After expanding, I got (4a2 + 4a + 1) - 6a - 3. Then, 4a2 - 2a - 2. Finally, I simplified it to get 2(2a2 - a) - 2. (2a2 - a) is an integer because it is the difference of two integers. However, this does not match up with the definition of odd, which is z = 2a + 1. This means that there is not at least one non-negative integer z, z2 - 3z is an odd integer. Therefore, the statement that for every non-negative integer z, z2 - 3z is an even integer is true.

    I got confused somewhere down the line and I don't think that the solution I came up with is correct. I would really appreciate some assistance with this question.
     
  2. jcsd
  3. Oct 31, 2011 #2

    Mark44

    Staff: Mentor

    z2 - 3z = z(z - 3).

    Look at two cases - one in which z is odd and the other in which z is even. For each case, say something about z - 3.
     
  4. Oct 31, 2011 #3

    eumyang

    User Avatar
    Homework Helper

    EDIT: Withdrawn. What Mark44 said above is much simpler. :biggrin:
     
  5. Oct 31, 2011 #4
    Thanks so much for the quick reply! I didn't think of breaking down z2 - 3z to get z(z - 3). I substituted z for 2a+1 for odd and 2a for even into z(z-3), but I got the same results that I got from substituting 2a+1 and 2a into z2 3z: 2a(2a - 3) for even and 4a2 - 2a - 2 for odd.

    Why am I only supposed to say something about (z-3) for each case? Why not for z(z-3). Does (z-3) represent an integer and could be substituted for a in 2a+1 (odd) or 2a (even)? If that makes any sense!
     
  6. Oct 31, 2011 #5

    eumyang

    User Avatar
    Homework Helper

    If z is even, is z-3 even or odd? What can you say about their product?
     
  7. Oct 31, 2011 #6
    If z is even (z = 2a), wouldn't the product of z and z-3 be even since any number that is multiplied by an even number is even? And if z is odd (z = 2a+1), would the product of z and z-3 be odd as well? I'm not sure how to show this using the definitions of odd and even since I'm left with 2 (2a2 - a) - 2 when I use the definition of odd to substitute into the equation z(z-3) and it does not correspond to 2a + 1.
     
  8. Oct 31, 2011 #7

    eumyang

    User Avatar
    Homework Helper

    If z is odd (z = 2a +1), then
    z - 3 = 2a + 1 - 3 = 2a - 2.
    So is z-3 odd or even?
     
  9. Oct 31, 2011 #8
    z - 3 = 2a - 2
    = 2*(a-1)

    (a-1) is an integer since it is the sum or difference of two integers, so it would be equivalent to 2 * (integer) which is the same as saying 2a since a represents an integer. This means that z-3 is even.

    And if z is even, then z-3 would be even as well with the reasoning shown as follows:

    z -3 = 2a - 3
    z = 2a - 3 + 3
    z = 2a

    Is this reasoning correct?
     
  10. Oct 31, 2011 #9

    Mentallic

    User Avatar
    Homework Helper

    No, we took the case where z is odd, so let z=2a+1, then z-3=2a+1-3=2a-2=2(a-1) which is even. Now we have an odd times an even.
     
  11. Oct 31, 2011 #10

    eumyang

    User Avatar
    Homework Helper

    No. You're mixing up the two cases, it looks like.

    Case 1. If z is even (z = 2a), then z - 3 is odd. So z * (z - 3) is even.
    Case 2. If z is odd (z = 2a + 1), then z - 3 is even [z - 3 = 2(a - 1)]. So z * (z - 3) is also even.

    That's it!
     
  12. Oct 31, 2011 #11

    Mark44

    Staff: Mentor

    And you don't even have to add the bits about z = 2a or z = 2a + 1. If z is even, it's pretty evident about z - 3 being odd. If z is odd, clearly z-3 is even. In either case you have an odd number times an even number, which gives an even number.
     
  13. Oct 31, 2011 #12
    Thank you very much for the clarification. This has been very helpful. I understand why if z is odd, then z-3 is even. However, I still don't get if z is even, why z-3 is odd. If z is even, then z = 2a. z - 3 = 2a - 3. How is 2a - 3 odd? Is it because of the -3?
     
  14. Oct 31, 2011 #13

    eumyang

    User Avatar
    Homework Helper

    Because
    2a - 3
    = 2a - 4 + 1
    = 2(a - 2) + 1
    (or 2 times some integer, plus 1)
     
  15. Nov 1, 2011 #14

    Mentallic

    User Avatar
    Homework Helper

    Think about it intuitively. We have some even number, then we take 3 away from that so taking away 1 gives us an odd, then even, then odd.
    Or in an even quicker fashion, taking away 2 obviously gives us the next even number down, so taking away 3 gives us an odd.
    And then extending this to the general case, taking away 2n from an even number for some integer n gives us another even number, then taking away 2n+1 gives us an odd number.
     
  16. Nov 1, 2011 #15
    Ohh, I understand it now. I didn't see the connection with -4 + 1 and -3 before. As a distance education student, I really appreciate the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete Mathematics: Proof problem for even integer
  1. Integer Problem (Replies: 4)

  2. Discrete Mathematics (Replies: 2)

  3. Problems on integers (Replies: 8)

Loading...