Proof by Contrapositive

Show your work for each problem.

1.
Which statement is the contrapositive of "If $n^2$ is even, then $n$ is even"?
1. a)If $n^2$ is odd, then $n$ is odd
2. b)If $n$ is odd, then $n^2$ is even
3. c)If $n$ is odd, then $n^2$ is odd
4. d)If $n$ is even, then $n^2$ is even
Answer: If $n$ is odd, then $n^2$ is odd
The contrapositive of $p \to q$ is $\neg q \to \neg p$ : "if $n$ is odd, then $n^2$ is odd". The first choice is the converse, the second is the inverse, the last one is not related.
2.
You want to prove "If $xy$ is odd, then $x$ and $y$ are both odd" by contrapositive. What do you assume at the start?
1. a) $x$ and $y$ are both odd
2. b) $x$ and $y$ are both even
3. c) $x$ is even or $y$ is even
4. d) $xy$ is even
Answer: $x$ is even or $y$ is even
The conclusion " $x$ and $y$ are odd" fails as soon as one number is even, so its negation is " $x$ is even or $y$ is even". " $xy$ is even" is what you must prove, and "both even" misses cases.
3.
What is the negation of " $x \geq 5$ or $y \geq 5$ "?
1. a) $x \leq 5$ and $y \leq 5$
2. b) $x < 5$ or $y < 5$
3. c) $x < 5$ and $y < 5$
4. d) $x > 5$ and $y > 5$
Answer: $x < 5$ and $y < 5$
"Not ( $a$ or $b$ )" means "not $a$ and not $b$ ", and the negation of $x \geq 5$ is $x < 5$ . So the answer is " $x < 5$ and $y < 5$ ". With $\leq$ the value 5 would wrongly be included.
4.
In a proof by contrapositive of $p \to q$ you start by assuming $\neg q$ . What must you reach at the end?
1. a) $\neg p$
2. b) $p$ and $\neg q$ at the same time
3. c) $q$
4. d)Any contradiction
Answer: $\neg p$
A proof by contrapositive proves $\neg q \to \neg p$ , so from $\neg q$ you must reach exactly $\neg p$ . Looking for any contradiction, or assuming $p$ and $\neg q$ together, is proof by contradiction.
5.
For which statement is a proof by contrapositive clearly the better choice than a direct proof?
1. a)If $n$ is even, then $n^2$ is even
2. b)If $a$ and $b$ are even, then $a + b$ is even
3. c)If $5n + 1$ is even, then $n$ is odd
4. d)If $n$ is odd, then $n + 1$ is even
Answer: If $5n + 1$ is even, then $n$ is odd
In the other three statements the hypothesis is concrete ( $n = 2k$ , $a = 2m$ and $b = 2j$ , $n = 2k + 1$ ), so a direct proof is quick. " $5n + 1$ is even" says little about $n$ , but the contrapositive is easy: if $n = 2k$ , then $5n + 1 = 10k + 1 = 2(5k) + 1$ is odd.
6.
In the truth table, look at the row where $p$ is true and $q$ is false. What is the value of $\neg q \to \neg p$ in that row? Type 1 for true and 0 for false.
Answer: 0
With $p$ true and $q$ false: $\neg q$ is true and $\neg p$ is false, so $\neg q \to \neg p$ is false (0). This is exactly the row where $p \to q$ is false too: the two columns agree.
7.
Contrapositive proof of "if $n^2$ is odd, then $n$ is odd": assume $n = 2k$ , so $n^2 = 4k^2 = 2(2k^2)$ . For $k = 7$ , what is $2k^2$ ?
Answer: 98
$2k^2 = 2 \cdot 49 = 98$ . Check: $n = 14$ and $n^2 = 196 = 2 \cdot 98$ , which is even, as the contrapositive says.
8.
In the proof that an odd $n$ gives an odd $n^2$ , we write $n = 2k + 1$ and $n^2 = 2(2k^2 + 2k) + 1$ . For $n = 9$ we have $k = 4$ . What is $2k^2 + 2k$ ?
Answer: 40
$2k^2 + 2k = 32 + 8 = 40$ . Check: $2 \cdot 40 + 1 = 81 = 9^2$ , an odd number.
9.
The contrapositive of "if $x + y \geq 10$ , then $x \geq 5$ or $y \geq 5$ " says: if $x < 5$ and $y < 5$ , then $x + y < 10$ . For integers $x$ and $y$ with $x < 5$ and $y < 5$ , what is the largest possible value of $x + y$ ?
Answer: 8
The largest choices are $x = 4$ and $y = 4$ , so $x + y = 8$ , which is less than 10, as the contrapositive predicts.
10.
To prove "if $n^2 - 6n + 5$ is even, then $n$ is odd" by contrapositive, assume $n = 2k$ . Then $n^2 - 6n + 5 = 2(2k^2 - 6k + 2) + 1$ . For $k = 3$ , what is $2k^2 - 6k + 2$ ?
Answer: 2
$2k^2 - 6k + 2 = 18 - 18 + 2 = 2$ . Check: $n = 6$ gives $36 - 36 + 5 = 5 = 2 \cdot 2 + 1$ , an odd number.
11.
Check the contrapositive of "if $n^2$ is even, then $n$ is even" with the odd number $n = 11$ .
Answer: $121 = 2 \cdot 60 + 1$
1. What is $n^2$ ? 121
2. Write $121 = 2m + 1$ . What is $m$ ? 60
3. What is the remainder when $121$ is divided by 2? 1
12.
Prove "if $3n + 2$ is odd, then $n$ is odd" by contrapositive and check it with $k = 4$ .
Answer: 13
1. Assume $n$ is even: $n = 2k$ . For $k = 4$ , what is $n$ ? 8
2. What is $3n + 2$ ? 26
3. In general $3n + 2 = 6k + 2 = 2(3k + 1)$ . What is $3k + 1$ for $k = 4$ ? 13
13.
Contrapositive of "if $xy$ is odd, then $x$ and $y$ are odd", case " $x$ is even". Follow the proof with $x = 6$ and $y = 7$ .
Answer: 21
1. Write $x = 2k$ . What is $k$ ? 3
2. What is $xy$ ? 42
3. The proof writes $xy = 2(ky)$ . What is $ky$ ? 21
14.
Compare the columns $p \to q$ and $\neg q \to \neg p$ in the truth table with 4 rows.
Answer: 0
1. In how many of the 4 rows is $p \to q$ true? 3
2. In how many rows is $\neg q \to \neg p$ true? 3
3. In how many rows do the two columns have different values? 0
15.
Prove by contrapositive: for real numbers $x$ , $y$ , $z$ , if $x + y + z \geq 30$ , then $x \geq 10$ or $y \geq 10$ or $z \geq 10$ .
Answer: $x + y + z < 30$
1. The negated conclusion is " $x < 10$ and $y < 10$ and $z < 10$ ". How many inequalities do you assume? 3
2. Add the inequalities: $x + y + z$ is less than which number? 30
3. Can $x + y + z \geq 30$ hold then? Type 1 for yes, 0 for no. 0
16.
Statement: if $n^2 - 6n + 5$ is even, then $n$ is odd. Check the contrapositive with $n = 2k$ and $k = 5$ .
Answer: 22
1. What is $n$ ? 10
2. What is $n^2 - 6n + 5$ ? 45
3. Write the result as $2m + 1$ . What is $m$ ? 22
17.
Prove by contrapositive: if 7 numbers have a sum $S$ greater than 63, then at least one of them is greater than 9.
Answer: $S \leq 63$
1. Negated conclusion: every number is at most which value? 9
2. What is the largest possible sum of 7 such numbers? 63
3. Can the sum then be greater than 63? Type 1 for yes, 0 for no. 0
18.
Prove "if $n^2$ is not divisible by 3, then $n$ is not divisible by 3" by contrapositive and check it with $k = 7$ .
Answer: 147
1. Assume $n$ is divisible by 3: $n = 3k$ . For $k = 7$ , what is $n$ ? 21
2. What is $n^2$ ? 441
3. In general $n^2 = 9k^2 = 3(3k^2)$ . What is $3k^2$ for $k = 7$ ? 147