Expert: Sherry Wallin - 4/26/2011

Question
Prove the following conjecture using each of the two methods introduced in this module -- contrapositive and contradiction.

Conjecture:  Let m and n be integers.  If 3m - n is even and m is odd, then n is odd.

Answer
Hi Melissa~

Let p = 3m-n is even and q = m is odd and r = n is odd, then this proposition is If p & Q then r. The contrapositive is ~r then ~(p & q) which is equivalent to ~r the ~p OR ~q which is the same as saying n is even implies either 3m-n is odd or m is even.

Proof:
n is even means there exists an integer, call it k, such that n = 2k. 3m-n is then equal to 3m-2k = m + 2m -  2k = m + 2(m-k).  If m is even then 3m is even and there exists an integer j such that m = 2j, so now we have 3(2j) - 2k = 2(3j-k) which is even. If m is odd then there exists an integer h such that

m = 2h+1 and then 3m-n

= 3(2h+1) - 2k

= 6h + 3 -2k

= 2(3h-k) + 3

= 2(3h-k) + 2 + 1

= 2[(3h-k+1)] + 1 => 3m-n is odd  

Thus 3m-n will be even as long as m is even and 3m-n will be odd if m is odd but either way either 3m-n is odd or m is even.


Proof by contradiction is easier:

Assume 3m-n is even and m is odd and also assume the negation of the conclusion so instead of n is odd assume n is even.

Since m is odd there exists and integer p such that m = 2p+1 and n is even there exists another integer q such that n = 2q.
Now 3m-n

= 2p+1 - 2q

= 2p-2q+1

= 2(p-q)+1 which is clearly an odd #  **** this is your contradiction because we assumed that 3m-n was even


Math Prof