Trivial on odd and even. Prove by cases

[flyingpig]

Homework Statement

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 ?

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.

 

[gb7nash]

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

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.

 

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

 

[flyingpig]

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.

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

 

[flyingpig]

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.

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

 

[flyingpig]

Deleted my incorrect comment

Yeah I did that in Case 2 for 1) but I cannot proceed because ab is not odd.

 

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

 

[gb7nash]

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?

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

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

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

 

[flyingpig]

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.

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?

 

[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)

 

[flyingpig]

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)

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

 

[gb7nash]

I don't know what WLOG means.

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)

 

[ArcanaNoir]

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

 

[flyingpig]

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

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

 

[ArcanaNoir]

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

 

[flyingpig]

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

 

[ArcanaNoir]

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

I already said that.

 

[flyingpig]

nvm i solved it using truth value table