# Homework Help: Trivial on odd and even. Prove by cases

1. Oct 26, 2011

### flyingpig

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

For $$a,b, \in Z$$, prove that if ab is odd, then $$a^2 + b^2$$ 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 $$k, l \in \mathbb{Z}$$

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

ab = (2k + 1)(2l + 1) = $$4kl + 2k + 2l + 1 = 2(2lk + k + l) + 1$$

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

$$(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)$$

$$(2k^2 + k + 2l^2 + l + 1) \mathbb{Z}$$, so $$a^2 + b^2$$ 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 $$s, t \in \mathbb{Z}$$

a = 2s
b = 2t + 1

Then

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

$$st + s \in \mathbb{Z}$$, so ab is unfortunately even

Something went wrong here, because I will only have one case.

2. Oct 26, 2011

### gb7nash

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.

3. Oct 26, 2011

### ArcanaNoir

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.

4. Oct 26, 2011

### flyingpig

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 $$m,n \in \mathbb{Z}$$

a = 2m
b = 2n

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

$$2mn \in \mathbb{Z}$$, hence ab is even and not odd. Therefore (red statement) does not hold

5. Oct 26, 2011

### flyingpig

I thought there was a reason why it was called Prove by Cases

6. Oct 26, 2011

### flyingpig

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
7. Oct 26, 2011

### ArcanaNoir

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.

8. Oct 26, 2011

### gb7nash

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...

9. Oct 26, 2011

### flyingpig

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?

10. Oct 26, 2011

### ArcanaNoir

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)

11. Oct 26, 2011

### flyingpig

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

12. Oct 26, 2011

### gb7nash

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)

13. Oct 26, 2011

### ArcanaNoir

ah, without loss of generality. I like that. I used "likewise" but it always felt barely acceptable...

14. Oct 26, 2011

### flyingpig

I found that if you use complicated gibberish it makes you look smarter

15. Oct 26, 2011

### ArcanaNoir

And confuses the graders. Although sometimes they dock points when they don't understand >_<

16. Oct 26, 2011

### flyingpig

You know, just interesting. I found that if a and b are both even, a^2 + b^2 is actually even too.

17. Oct 26, 2011