Exercises: Direct Proof and Contraposition

Proof-writing is a skill, and skills need reps. These exercises run from mechanical warm-ups through full proofs, code, modeling, and error-hunting. Difficulty markers: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the daggered (†) and odd-numbered problems live in the appendix answers-to-selected.md — write your own attempt first, then check.

For every proof, the rubric rewards the same four things the chapter drilled: a clearly named strategy ("direct" or "by contraposition"), a correct setup (an arbitrary variable, the right hypothesis assumed), explicit use of definitions (unpack the hypothesis, repackage the goal), and a clean close that states the actual claim and ends with $\blacksquare$.

A note on definitions. Use the chapter's definitions verbatim: $n$ is even iff $n = 2k$ for some integer $k$; $n$ is odd iff $n = 2k+1$ for some integer $k$; $a \mid b$ (with $a \neq 0$) iff $b = ac$ for some integer $c$. A proof that reasons from a mental picture instead of these is not a proof.

Part A — Warm-ups (⭐)

4.1 † Unpack each statement into its existential ("there exists…") form and give the witness: (a) $4 \mid 28$; (b) $-72$ is even; (c) $a \mid 0$ for any nonzero integer $a$.

4.2 For the claim "for every integer $n$, $n^2 + 3n$ is even," fill a table of $n^2 + 3n$ for $n = -2, -1, 0, 1, 2, 3$ and confirm each value is even. Then state, in one sentence, why this table is not a proof.

4.3 † Classify each as a theorem, lemma, corollary, or conjecture: (a) "every even integer greater than 2 is the sum of two primes"; (b) "since we just proved the result for all $n$, in particular it holds for $n = 100$"; (c) a small parity fact proved only so a later proof reads cleanly; (d) "the sum of the first $n$ odd numbers is $n^2$" (which you can and will prove).

4.4 Write the contrapositive and the converse of each, then say which one is logically equivalent to the original: (a) "if $n$ is divisible by 10, then $n$ is divisible by 5"; (b) "if a graph is a tree, then it is connected"; (c) "if $x$ is irrational, then $x \neq 0$."

4.5 † In Example 1 of §4.3 (odd squared is odd), identify the exact line that performs the unpack and the exact line that performs the repackage.

4.6 True or false, with a one-line justification from the definition: (a) $1 \mid n$ for every integer $n$; (b) $0$ is even; (c) $7 \mid 7$.

Part B — Prove it (⭐⭐)

4.7 † (Scaffolded — fill in each blank.) Theorem. For every integer $n$, if $n$ is even, then $5n + 4$ is even. Proof. Let $n$ be an arbitrary integer and assume $n$ is even. By definition, there is an integer $k$ with $n = \underline{\hphantom{xxxx}}$. Then $$5n + 4 = 5(\underline{\hphantom{xxxx}}) + 4 = 10k + 4 = 2(\underline{\hphantom{xxxxx}}).$$ Let $m = \underline{\hphantom{xxxxx}}$; since $k$ is an integer, $m$ is an integer, and $5n + 4 = 2m$. By the definition of even, $5n + 4$ is even. Since $n$ was arbitrary, the statement holds for all integers $n$. $\blacksquare$

4.8 Theorem. For all integers $a, b, c$ with $a \neq 0$: if $a \mid b$ and $a \mid c$, then $a \mid (b - c)$. (Mimic Example 2 of §4.3, but subtract instead of add. This is the difference version of that lemma — the exact fact Chapter 22 leans on for the Euclidean algorithm.)

4.9 † Theorem. For all integers $a, b, c$ with $a \neq 0$: if $a \mid b$, then $a \mid bc$. (One hypothesis, one witness. Unpack $a \mid b$, multiply, repackage.)

4.10 Theorem. For every integer $n$, the integer $n^2 + n + 2$ is even. (Hint: $n^2 + n$ factors — recall the opening example of §4.1 — and adding an even number keeps it even. State which earlier result you are reusing.)

4.11 † Theorem (prove by contraposition). For every integer $n$, if $3n + 5$ is even, then $n$ is odd. State the contrapositive explicitly before you prove it.

4.12 Theorem (prove by contraposition). For every integer $n$, if $n^2 - 6n + 5$ is even, then $n$ is odd. (Direct attack stalls — you cannot extract $n$ from a statement about $n^2$. Contrapose: assume $n$ is even, and show $n^2 - 6n + 5$ is odd.)

4.13 † Theorem (biconditional — both directions). For every integer $n$, $n$ is even if and only if $7n$ is even. Prove each direction, and say which direction (if either) is more naturally attacked by contraposition.

4.14 Theorem. For all integers $a$ and $b$, if both $a$ and $b$ are odd, then $a + b$ is even. (This is Case 2 of Example 5 in §4.4, standing on its own. A clean direct proof.)

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it — hand-trace the result and include an # Expected output: comment, matching the book's convention. Keep each function short and clear.

4.15 † Write a predicate same_parity(a, b) that returns True exactly when integers a and b have the same parity (both even or both odd), using only %. Then write three lines that print its value on (4, 10), (3, 8), and (-7, 5), and give the expected output. (This is the predicate behind Example 5 of §4.4.)

4.16 Write a function repackage_odd_square(k) that, given an integer k, returns the witness integer m such that $(2k+1)^2 = 2m + 1$ — i.e., it returns the "$m$" that the proof of Example 1 manufactured. Print it for k = 0, 1, 5 and verify by hand that $2m + 1$ really equals $(2k+1)^2$ in each case.

4.17 † Using the chapter's find_counterexample(predicate, domain) (from the Project Checkpoint), write three lines that test the claim "for every integer $n$, if $n$ is odd then $5n + 3$ is even" on the domain range(-50, 51). What output would support the claim, and what output would refute it? (You will prove or disprove this same claim in Exercise 4.24 — do not prove it here.)

Part D — Find the error (⭐⭐)

Each "proof" below is broken. Run the chapter's reading routine (name the form → find the strategy → check the setup → justify each step → check the close) and state precisely which part fails and why.

4.18 † Claim. For every integer $n$, if $n^2$ is even, then $n$ is even. "Proof." "The contrapositive is: if $n$ is even, then $n^2$ is even. Assume $n$ is even, so $n = 2k$. Then $n^2 = 4k^2 = 2(2k^2)$ is even. This proves the contrapositive, so we are done. $\blacksquare$" — The algebra is correct and the conclusion is even true. So what, precisely, is wrong with this as a proof of the stated claim? (Hint: write out the actual contrapositive of the claim and compare what the student labeled as "the contrapositive." This is the trap from the §4.4 Find-the-Error box.)

4.19 Claim. For all integers $a$ and $b$, if $a \mid b$, then $a \mid (b + 1)$. "Proof." "Since $a \mid b$, write $b = ak$. Then $b + 1 = ak + 1 = a(k) + 1$, so $a$ divides $b + 1$. $\blacksquare$" — Find the bug, and give a one-line counterexample showing the claim itself is false.

4.20 † Claim. For all integers $a$ and $b$, if $a$ is even and $b$ is even, then $a = b$. "Proof." "Since $a$ is even, $a = 2k$. Since $b$ is even, $b = 2k$. Therefore $a = 2k = b$. $\blacksquare$" — Name the specific pitfall from §4.5 this commits, and give a counterexample.

4.21 Claim. For every integer $n$, if $n$ is odd, then $n^2$ is odd. "Proof." "Take $n = 1$: $n^2 = 1$, odd. Take $n = 3$: $n^2 = 9$, odd. Take $n = 5$: $n^2 = 25$, odd. The pattern is clear, so the claim holds for all odd $n$. $\blacksquare$" — The claim is true, but the proof is not a proof. Which pitfall is this, and what is the one-word fix to the setup?

Part E — Model it (⭐⭐⭐)

4.22 † (Model it.) A build server runs a job only when the commit number is divisible by 4 ("every 4th commit triggers a full build"). A teammate claims: "Every commit that triggers a full build also passes the lightweight check, which fires on every even commit number." Translate this claim into a divisibility statement of the form "for every integer $n$, if $\dots$ then $\dots$," then prove it using the chapter's tools. (You are proving "if $4 \mid n$ then $2 \mid n$.")

4.23 (Model it.) A two-factor login emits a session token equal to $u + p$, where $u$ is a user-ID parity bit's source integer and $p$ a one-time-code source integer. A logging rule says: "the token is logged as 'mismatch' exactly when the token is odd." Your security lead conjectures: "a token is logged as 'mismatch' if and only if $u$ and $p$ have opposite parity." (a) Translate this into a precise biconditional about integers $u$, $p$, and $u + p$. (b) Identify which single direction of the biconditional is exactly Example 5 of §4.4, and which direction you would attack by contraposition. (You do not have to write both full proofs — set up the structure and cite §4.4.)

Part F — Conjecture and test, then prove (⭐⭐⭐)

For each, first test the claim with code on a range of cases (write the code and its hand-derived # Expected output:), then either prove it or disprove it with a counterexample.

4.24 † Claim: for every integer $n$, if $n$ is odd, then $5n + 3$ is even. First test it with find_counterexample on range(-50, 51). Based on the output, decide whether to prove it (give a direct proof) or disprove it (give a counterexample).

4.25 Claim: for every integer $n$, if $n$ is even, then $n^2 + n + 1$ is prime. Test it on range(0, 30) with a small primality predicate you write. Report the first counterexample the code finds, then state in one sentence why "it was prime for the first several even $n$" never made this a theorem. (Connect to theme four of the book.)

4.26 † Claim: for all integers $a$ and $b$, if $a \mid b$ and $b \mid a$, then $a = b$. Test it by searching pairs (a, b) with a, b in range(-5, 6), a != 0, b != 0, for a pair where the hypothesis holds but $a \neq b$. Report what you find, then fix the claim so that it becomes true (state the corrected theorem — you do not need to prove the fix). (This is the flawed proof from §4.6; here you find the counterexample by code.)

Part G — Interleaved (mixing earlier chapters)

Keeping earlier techniques sharp is the point of interleaving. Each problem below pulls in Chapter 1, 2, or 3.

4.27 † (Ch. 1 + 4.) Build the truth table for $P \rightarrow Q$ and for $\neg Q \rightarrow \neg P$ side by side, and circle the two identical columns. Then explain, in one sentence, why this table — not any number of examples — is what licenses proof by contraposition.

4.28 (Ch. 2 + 4.) The statement "$a \mid b$" hides a quantifier. (a) Write "$a \mid b$" as a fully quantified statement. (b) Write its negation "$a \nmid b$" as a quantified statement, pushing the negation all the way in. (c) Which quantifier governs each?

4.29 † (Ch. 3 + 4.) A direct proof of $P \rightarrow Q$ "constructs" an inference rule. (a) Name it. (b) A classmate proves $Q \rightarrow P$ and claims to have proved $P \rightarrow Q$. Name the fallacy (Chapter 3) and explain its relationship to the converse.

4.30 (Ch. 2 + 4.) Write the negation of the universally quantified claim "$\forall n \in \mathbb{Z},\ (n \text{ odd} \rightarrow n^2 \text{ odd})$." Use your negation to explain exactly what object you would need to exhibit to disprove the claim — and why no such object exists.

4.31 † (Ch. 1 + 4, Deep Dive.) A biconditional $P \leftrightarrow Q$ is logically equivalent to $(P \rightarrow Q) \land (Q \rightarrow P)$ (Chapter 1). Use this to argue, in a short paragraph, why proving only the forward direction of "$n$ is odd iff $n^2$ is odd" leaves a genuine gap — and name a different "if and only if" claim where the converse is actually false, so the gap really matters.

4.32 (Ch. 3 + 4, Deep Dive.) Proof by contraposition replaces $P \rightarrow Q$ with $\neg Q \rightarrow \neg P$. Using only the inference rules of Chapter 3 (in particular modus tollens), explain why a correct direct proof of $\neg Q \rightarrow \neg P$, combined with a proof of $\neg Q$, lets you conclude $\neg P$ — and why this is the same logical content as the original conditional.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. Reference code for the "implement it" problems is in this chapter's code/exercise-solutions.py — but try them on paper first.