Further Reading: Direct Proof and Contraposition

This chapter is your first sustained practice writing proofs, so most of these pointers are about proof-writing as a craft — the form, the habits, and the standard catalog of techniques. Start with the textbook sections for more drill, branch to the proof-writing books if the shape of a proof still feels uncertain, and dip into the deeper dives once direct proof and contraposition feel automatic.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §1.7–1.8 The market-standard treatment of proof methods: direct proof, contraposition, vacuous and trivial proofs, plus the vocabulary of theorem/lemma/corollary/conjecture — exactly this chapter's territory, with a very large graded exercise bank. If you want more practice problems than we provide, this is the first place to go.

Epp, Discrete Mathematics with Applications (5th ed.), Chapter 4 (Elementary Number Theory and Methods of Proof) The clearest careful walk through direct proof about even, odd, and divisibility anywhere in the standard texts. Epp is unusually explicit about the "unpack the definition, repackage the conclusion" rhythm and about the common mistakes (proving the converse, arguing from examples), which makes it a near-perfect companion to §§4.2–4.5.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), proof chapter Freely available. A friendly, free treatment of direct proof and proof by contrapositive with worked parity and divisibility examples. Good if you want a second voice on the same material at no cost.

On proof-writing as a craft

Velleman, How to Prove It (3rd ed.), chapters on proof strategies The gentlest careful book on how to construct a proof — it teaches you to read the logical form of a statement and let it dictate the strategy, which is precisely the §4.5 "name the form, choose the strategy" template. If the blank page is still intimidating, this is the standard recommendation.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), early proof chapters Freely available. The most CS-flavored introduction to proofs in print: it frames a proof as an argument that defeats a skeptic and develops direct proof, contraposition, and the well-definedness of proof methods with a programmer's sensibility. Its spirit matches this book's closely.

On why proofs (not tests) guarantee correctness

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), §1.1 and the correctness discussions The canonical reference for the idea that a stated property must be proved for all inputs, not merely tested. Reading its framing of correctness alongside §4.1 reinforces theme two — "passes the tests" is not "is correct."

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 4 (Number Theory), divisibility sections Where divisibility — the anchor introduced in §4.2 — gets the serious development it deserves, including the $\mid$ relation and its basic theorems proved with care. Denser than this chapter, but it is where the "$a \mid b$ and $a \mid c$ imply $a \mid (b \pm c)$" facts you proved here grow into the machinery of Chapter 22.

Suggested order

  1. Re-read §§4.2–4.5 here, then do Epp Chapter 4's direct-proof and contrapositive exercises for drill — they are the closest match to our examples.
  2. If the form of proofs still feels shaky, read the relevant chapters of Velleman, How to Prove It.
  3. Read the early proof chapters of MIT 6.042 for the CS framing and the "defeat the skeptic" picture.
  4. Skim CLRS §1.1 to connect proof to algorithm correctness (theme two), then do this chapter's "Conjecture and test, then prove" exercises (Part F).
  5. Save Concrete Mathematics Chapter 4 for when you reach Chapter 22 (gcd and the Euclidean algorithm), where the divisibility facts proved here do real work.