Discrete Math - Direct or Contrapositive
Favorites|Homepage
Subscriptions | sitemap
HOME > > Discrete Math - Direct or Contrapositive

Discrete Math - Direct or Contrapositive

[From: ] [author: ] [Date: 13-01-29] [Hit: ]
mn - (m + n) is even.Therefore, (m - 1)(n - 1) = mn - m - n + 1 = mn - (m + n) + 1 is odd.Since the only way that the product of two integers can be odd is when both integers are odd, m - 1 and n - 1 must both be odd.We conclude that m and n are both even.......
if m + n and mn have the same parity, then m and n are both even

which method do i use? direct or contrapositive, i dont really understand when to use the right method

-
Direct would be significantly more complicated because you would need to formulate parity in algebra and look for a way to simplify the relation. I would use a proof by contradiction here because the alternatives to both even are simply both odd and 1 odd, 1 even.
Contradiction:
(1)Assume m = 2a, n = 2b + 1 where a and b are integers ( so m is even and n is odd).
m + n = (2a + 2b + 1) must be odd
mn = 2a*(2b + 1) must be even, hence they do not have the same parity.

(2) Assume m=2a + 1, n = 2b + 1 where a and b are integers.
m + n = 2*(a+b+1) must be even
mn = (2a + 1)(2b + 1) = 4b^2 + 2*(a + b) + 1 must be odd, so parity different again.

To be fully complete you should also prove that it is possible for m + n and mn to have the same parity (this is obvious, an example such as m=4 n=6 is sufficient to prove it).

-
I am assuming that m and n represent integers.
The proof could be done directly or by contrapositive; some proofs can be done in more than one way.

Method 1 (direct): Since m + n and mn have the same parity, mn - (m + n) is even. Therefore, (m - 1)(n - 1) = mn - m - n + 1 = mn - (m + n) + 1 is odd. Since the only way that the product of two integers can be odd is when both integers are odd, m - 1 and n - 1 must both be odd. We conclude that m and n are both even.

Method 2 (contrapositive, or indirect): Assume temporarily that m and n are not both even. Then m is odd or n is odd.

If m is odd, then m + n and n have opposite parity since odd+odd=even and odd+even=odd, while mn and n have the same parity since odd*odd=odd and odd*even=even. So m + n and mn have opposite parity, contradicting the given fact that m + n and mn have the same parity.

If n is odd, then m + n and m have opposite parity since odd+odd=even and even+odd=odd, while mn and m have the same parity since odd*odd=odd and even*odd=even. So m + n and mn have opposite parity, contradicting the given fact that m + n and mn have the same parity.

So in either case, we obtain a contradiction. Our temporary assumption that m and n are not both even is false, so we conclude that m and n are both even.

Lord bless you today!

-
Try the contrapositive.

Suppose that at least one of m and n is odd.

If both m and n are odd, then m + n is even and mn is odd.
If, say, m is odd and n is even, then m + n is odd and mn is even.

So in either case m + n and mn have opposite parity.

Thus by contraposition the original claim holds true as well.
1
keywords: Discrete,or,Direct,Contrapositive,Math,Discrete Math - Direct or Contrapositive
New
Hot
© 2008-2010 http://www.science-mathematics.com . Program by zplan cms. Theme by wukong .