Valid Reasoning

Question

How do you prove that if n is an integer and 3n+2 is even, then n is even using (a) proof by contraposition (b) proof by contradiction?

Answer 1

(a) In a proof by contraposition we use the fact that p→q is equivalent to its contrapositive ¬q→¬p. In your question we would need a direct proof that if n is odd (¬q) then 3n+2 is odd (¬p).

 

            Statement                                            Reason

 

            1. ∃ an integer k s.t n=2k+1                  1. by the definition of odd number

            2. 3n+2 = 3(2k+1)+2                            2. substitution

            3. 3n+2 = 6k +3 +2                              3. distributive law

            4.          = 6k +4 +1                              4. "algebra"

            5.          = 2(3k+2)+1                            5. factor 2

            6. j=3k+2 is an integer                          6. the integers are closed under multiplication and addition

            7. 3n+2=2j+1 is an odd number             7. by definition of odd number 

 

(b) In a proof by contradiction (which is very similar) we immediately assume the opposite of what we want to prove is true, namely that n is NOT even and then proceed to show that we end up with a contradiction.

 

I'll start this one for you:

 

           1. Assume n is odd                             1. Start of proof by contradiction

           2. n=2k+1 for some integer k              2. Def of odd number

 

Try to finish this on your own. Remember your goal is to have your last line contradict something you know or are given as being true.

 

If you need more help add a comment here.