For the following, you must use good proof technique; follow the structure in th
ID: 3145001 • Letter: F
Question
For the following, you must use good proof technique; follow the structure in the Course Notes/videos.
Clearly state what is assumed [the premises] and state reasons for each step.
The reader must be able to easily follow your reasoning.
When a particular proof technique is stated, you must use that proof technique.
1)
State what must be proved for the “forward proof” part of proving the following biconditional:
For any positive integer n, n is even if and only if 3n+2 is even.
Complete a DIRECT proof of the “forward proof” part of the biconditional stated in part a.
2)
State what must be proved for the “backward proof” part of proving the following biconditional:
For any positive integer n, n is even if and only if 3n+2 is even.
Complete a proof by CONTRADICTION of the “backward proof” part of the biconditional stated in part a.
3)
State the CONTRAPOSITIVE of the following conditional statement:
For all integers n, if 3n+1 is odd, then n is even.
Complete an INDIRECT proof [by proving the CONTRAPOSITIVE you wrote in part a.] to show the following statement is true. Remember to state the final conclusion after completing the proof of the contrapositive.
For all integers n, if 3n+1 is odd, then n is even.
4)
Rewrite the following statement in the form “ x, y, P(x,y)”. Clearly indicate the domain of discourse for x and y and state what the predicate P(x,y) represents.
The product of a rational number and an irrational number is irrational.
Provide a counter-example that disproves the following proposition:
The product of a rational number and an irrational number is irrational.
Explanation / Answer
For any positive integer n, if n is even then 3n + 2 is even.
1. The forward proof should prove that n is even given that 3n + 2 is even.
Proof: It is given that n is an even integer.
Let n = 2k where k is an integer
=> 3n + 2 = 3*2k + 2
=> 3n + 2 = 2*3k + 2
=> 3n + 2 = 2 (3k + 1)
Let l = 3k + 1 where l is an integer
=> n = 2l
=> n is even.
2. The backward proof should prove that n is even given that 3n + 2 is even.
Proof by contradiction: It is given that 3n + 2 is an even integer.
Let us assume n is odd. Let n = 2k + 1 where k is an integer.
=> 3n + 2 = 3*(2k + 1) + 2
=> 3n + 2 = 2*3k + 3 + 2
=> 3n + 2 = 2*3k + 4 + 1
=> 3n + 2 = 2 (3k + 2) + 1
Let l = 3k + 2 where l is an integer
=> 3n + 2 = 2l + 1
=> 3n + 2 is odd which contradicts with the given statement that 3n + 2 i even
Therefore by contradiction, n i even.
3. For all integers n, if 3n+1 is odd, then n is even
The contrapositive is if n is not even, 3n + 1 is not odd
Proof by contrapositive: Since n is not even, it is odd
Let n = 2k + 1 where k is an integer
=> 3n + 1 = 3(2k + 1) + 1
=> 3n + 1 = 3*2k + 3 + 1
=> 3n + 1 = 3*2k + 4
=> 3n + 1 = 2(3k + 2)
Let l = 3k + 2 where l is an integer
=> 3n + 1 = 2l
=> 3n + 1 is even
=> 3n +1 is not odd.
4. The product of a rational number and an irrational number is irrational.
For all rational numbers x and y, their product is irrational.
x, y, P(x,y)
where P(x,y) means product of x and y is irrational.
Counter-example: Let p = 0 and q = 2
p is rational and q is irrational
P(p,q) = p*q = 0*2 = 0
=> P(p,q) is rational and not irrational.