Thread: Methods of Proof: Proof by Contrapositive

THIS IS NOT HOMEWORK! This is a practice problem from our textbook. Class link: Discrete Math I

Please correct if wrong:
My solution:
1) If n is odd, then n^2 is odd.
2) Suppose that n=2a+1, where a is an arbitrary integer.
3) Then n^2=(2a+1)^2 (Substitution)
<=> (2a+1)(2a+1) (Distributive law)
<=> 4a^2 + 4a + 1 (Distributive law, Associative law, Commutative law)
<=> 2(2a^2 + 2a) + 1 (Distributive law)
4) Since 2(2a^2 + 2a) + 1 = 2k + 1 (where k=2a^2 + 2a , and is therefore an integer) the proposition is true using the definition of odd: 2k + 1

Hey sflink.

You have show n implies n^2 but not the reverse.

We know that a number is either even or odd and if it's not one then its the other. We know even^2 is even, but what about the reverse?

Consider what happens when we multiply even*even and odd*odd. You can prove that even*even = even and odd*odd = odd for any odd numbers (even if they aren't the same necessarily). So this means odd*odd can't be even which means that if n = k*m and n is even then (k = ODD and m = ODD) can not occur. Similarly you have the same for even.

You can do this formally by assuming its true and then come to a contradiction (proof by contradiction is the most powerful tool in mathematics).

Originally Posted by chiro

You have show n implies n^2 but not the reverse.

chiro, n cannot imply n^2 because both are numbers, not propositions. Also, I am not sure what the "reverse" is. An implication has the converse, the inverse and the contrapositive. The OP proved the claim correctly, using reasoning by contrapositive, as required. My only remarks are that it should be noted that 1) is the contrapositive of the claim that is going to be proved and that 2) marks the start of a proof. Also, the line after the first <=> is obtained not by the distributive law but by substitution, namely, of the definition of the squaring function (.)² in terms of multiplication.

Thanks for that emakarov.

Sorry for the late reply. Thank you!