# Methods of Proof: Proof by Contrapositive

• Oct 28th 2012, 05:46 PM
Methods of Proof: Proof by Contrapositive
THIS IS NOT HOMEWORK! This is a practice problem from our textbook. Class link: Discrete Math I
Attachment 25447
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
• Oct 28th 2012, 09:11 PM
chiro
Re: Methods of Proof: Proof by Contrapositive

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).
• Oct 29th 2012, 07:16 AM
emakarov
Re: Methods of Proof: Proof by Contrapositive
Quote:

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 (.)2 in terms of multiplication.
• Oct 29th 2012, 08:14 PM
chiro
Re: Methods of Proof: Proof by Contrapositive
Thanks for that emakarov.
• Jan 10th 2013, 05:44 PM