Question

1. (i) Prove that if m and n are integers and mn is even, then m is even or n is even.
(ii) Show that if n is an integer and n3 + 5 is odd, then n is even using
(a) a proof by contraposition
(b) a proof by contradiction
(iii) Prove that if n is an integer and 3n + 2 is even, then n is even using
(a) a proof by contraposition
(b) a proof by contradiction
(iv)ProvethepropositionP(0),whereP(n)istheproposition”ifnisapositiveintegergreater than 1, then n2 > n.” What kind of proof did you use?
(v) Prove the proposition P(1), where P(n) is the proposition ” If n is a positive integer, then n2 ≥ n.” What kind of proof did you use?

Answer 1

1.(i) Suppose $mn$ is even. Then we can choose an integer $k$ such that $mn=2k.$ If $m$ is even, then there is nothing more to proove, so suppose $m$ is odd. Hence $m=2j+1$ for some integer $j.$ We get

$$(2j+1)n=2k$$ $$2jn+n=2k$$ $$n=2(k-jn)$$

Since $k-jn$ is an integer, it follows that $n$ is even.

(ii)

a) a proof by contraposition

The contrapositive is “If $n$ is odd, then $n^3+5$ is even.” Assume that $n$ is odd. We can now write $n=2k+1$ for some integer $k.$ Then

$$n^3+5=(2k+1)^3+5=8k^3+12k^2+6k+1+5=$$ $$=8k^3+12k^2+6k+6=2(4k^3+6k^2+3k+3).$$

Thus $n^3+5$ is two times some integer, so it is even by the definition of an even integer.

b) a proof by contradiction

Suppose that $n^3+5$ is odd and that $n$ is odd. Since $n$ is odd, the product of odd numbers is odd. So we can see that $n^3$ is odd. But if we subtract $5,$ then the difference between the two odd numbers $n^3+5$ and $n^3$ is even. Thus, our assumption was wrong and it is a contradiction. 

Therefore if $n$ is an integer and $n^3+5$ is odd, then $n$ is even.

(iii)

(a) a proof by contraposition 

(Contrapositive: If $n$ is even, then $3n+2$ is even) Suppose that the conclusion is false, i.e., that $n$ is even. Then $n=2k$ for some integer $k.$

Then $3n+2=3(2k)+2=6k+2=2(3k+1).$

Thus $3n+2$ is even, because it equals $2j$ for an integer $j=3k+1.$ So $3n+2$ is not odd. 

b) a proof by contradiction

Assume that the conclusion is false, i.e., that $n$ is even, and that $3n+2$ is odd. Then $n=2k$ for some integer $k$ and $3n+2=3(2k)+2=6k+2=2(3k+1).$

Thus $3n+2$ is even, because it equals $2j$ for an integer $j=3k+1.$This contradicts the assumption “$3n+2$ is odd”. This completes the proof by contradiction, proving that if $3n+2$ is odd, then $n$ is odd. 

(iv)

Note that $P(0)$ is that "If is a positive integer greater than $1$, then $0^2>0$ ".

Since " is a positive integer greater than $1$ " is false the the overall statement is true.

This is a vacuous proof.

(v)

Note that $P(1)$ is that "If $1$ is a positive integer, then $1^2\geq1$".

Since $1^2=1,$ then $P(1)$ is true.

This is a trivial proof.