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!

Trivial on odd and even. Prove by cases

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


    For [tex]a,b, \in Z[/tex], prove that if ab is odd, then [tex]a^2 + b^2[/tex] is even


    question 1

    ab = 2k + 1 for some k is integer (1)

    It doesn't seem logical to rearrange some a and b on (1)

    So I need the following

    product of two odd numbers is always odd,product of two even numbers is always even, product of odd and even integers is ???

    3. The attempt at a solution

    Case 1

    Let ab be odd, i.e. for [tex]k, l \in \mathbb{Z}[/tex]

    a = 2k + 1
    b = 2l + 1

    ab = (2k + 1)(2l + 1) = [tex]4kl + 2k + 2l + 1 = 2(2lk + k + l) + 1[/tex]

    (2lk + k + l) is an integer, so ab is odd. Then

    [tex](2k + 1)^2 + (2l + 1)^2 = 4k^2 + 2k + 1 + 4l^2 + 2l + 1 = 4k^2 + 2k + 2 + 4l^2 + 2l = 2(2k^2 + k + 2l^2 + l + 1)[/tex]

    [tex](2k^2 + k + 2l^2 + l + 1) \mathbb{Z}[/tex], so [tex]a^2 + b^2[/tex] is even (check)

    Case 2

    Let a be even and b be odd (WLOG --> means I shouldn't need to do a not odd and b is odd) and that [tex]s, t \in \mathbb{Z}[/tex]

    a = 2s
    b = 2t + 1

    Then

    ab = (2s)(2t + 1) = 4st + 2s = 2(st + s)

    [tex]st + s \in \mathbb{Z}[/tex], so ab is unfortunately even

    Something went wrong here, because I will only have one case.
     
  2. jcsd
  3. Oct 26, 2011 #2

    gb7nash

    User Avatar
    Homework Helper

    That's fine. You want to show, through cases, that a and b must both be odd. You've achieved this so far. You just need to show case 3, where a and b are both even and see what happens.
     
  4. Oct 26, 2011 #3
    Nothing really went wrong. The product of an odd number and an even number is always even, since there is a factor of two. The product of two even numbers is also even, for the same reason. Leaving you with only the case where a and b are both odd. The product of two odd numbers is always odd. You did prove that in that case a^2+b^2 is even. You can state it more concisely than you did by after showing ab is odd you can now say the product of odd numbers is odd therefore a^2 is odd and b^2 is odd, and the sum of two odd numbers is even.
     
  5. Oct 26, 2011 #4
    Why do I eve neeed case 2 and case 3? Is it not an accepted fact that the product of two even numbers isn't even?

    I showed that case 2 for ab didn't end up odd, i.e. If P fails, then [red]Q holds/does not hold[/red]

    Don't I need to show red?

    Case 3

    Let a and b be both even, i.e. for [tex]m,n \in \mathbb{Z}[/tex]

    a = 2m
    b = 2n

    ab = (2m)(2n) = 4mn = 2(2mn)

    [tex]2mn \in \mathbb{Z}[/tex], hence ab is even and not odd. Therefore (red statement) does not hold
     
  6. Oct 26, 2011 #5
    I thought there was a reason why it was called Prove by Cases
     
  7. Oct 26, 2011 #6
    Yeah I did that in Case 2 for 1) but I cannot proceed because ab is not odd.
     
    Last edited by a moderator: Oct 26, 2011
  8. Oct 26, 2011 #7
    That's right, the only reason for checking the three cases is to prove that you considered all cases. What if you only considered a and b are odd, thus ab is odd, thus a^2+b^2 is even.? Someone might say, but what if a is even and b is odd? It may seem silly in this case, but you can't do any assuming when it comes to proofs. (well, only intentional assuming).

    Suppose you were considering a proof about when ab was even? And then you considered only when a and b are both even. And then you found a^2+b^2 was also even, and then you claimed that ab is even implies a^2+b^2 is even ? This is not true since a is even and b is odd gives ab is even but gives a^2+b^2 is odd. So this is why you must show that you have considered all cases.
     
  9. Oct 26, 2011 #8

    gb7nash

    User Avatar
    Homework Helper

    Correct. However, unless you formally proved this in your proofs class, you don't "know" this yet.

    Correct. The main point is that we must find all cases for P to be true. You did this by looking at all three cases separately and seeing if P was true or false. Since the only case where P is true is a and b being odd...
     
  10. Oct 26, 2011 #9
    If p, then q

    p fails, q does not follow, so (if p fails, then q) fails then (if p, then q) fails and that is the key to Case 2 and 3.

    edit:
    I used WLOG correctly right?
     
  11. Oct 26, 2011 #10
    I don't know what WLOG means.
    You have the p/q down fine. Just don't leave the p test off your exam, you'll probably lose points. (test whether a odd and b even makes ab even...etc)
     
  12. Oct 26, 2011 #11
    http://en.wikipedia.org/wiki/Without_loss_of_generality

    Sorry my old linear algebra professor used it and said it was convenient when we do proofs. I just don't want to waste paper writing the same thing.

    thanks. I'll be sure to not forget the ps
     
  13. Oct 26, 2011 #12

    gb7nash

    User Avatar
    Homework Helper

    Without loss of generality. Basically, you'd use this to save time of reordering variables. (WLOG let a = even, b = odd covers any case where one variable is even and the other is odd)
     
  14. Oct 26, 2011 #13
    ah, without loss of generality. I like that. I used "likewise" but it always felt barely acceptable...
     
  15. Oct 26, 2011 #14
    I found that if you use complicated gibberish it makes you look smarter
     
  16. Oct 26, 2011 #15
    And confuses the graders. Although sometimes they dock points when they don't understand >_<
     
  17. Oct 26, 2011 #16
    You know, just interesting. I found that if a and b are both even, a^2 + b^2 is actually even too.
     
  18. Oct 26, 2011 #17
    I already said that.
     
  19. Oct 26, 2011 #18
    nvm i solved it using truth value table
     
    Last edited: Oct 26, 2011
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Trivial on odd and even. Prove by cases
  1. Even/odd case proof (Replies: 1)

Loading...