Appendix C: Proof Techniques Cheat Sheet

A one-stop reference for the proof methods developed in Part I (Chapters 4–7). For each: when to reach for it, its skeleton, and the classic example. Keep this page open while you work the exercises.

Choosing a technique

What are you proving?
├─ "If P then Q"            → try DIRECT proof; if stuck, try CONTRAPOSITION
├─ "P is impossible / not"  → CONTRADICTION
├─ "for all n >= n0, P(n)"  → INDUCTION (or STRONG induction if you need several previous cases)
├─ "there exists x, P(x)"   → EXISTENCE (construct one, or argue non-constructively)
├─ "exactly one x, P(x)"    → EXISTENCE + UNIQUENESS
├─ "for all x, P(x)" is FALSE → find a COUNTEREXAMPLE
└─ several cases cover all x → PROOF BY CASES

Direct proof (Chapter 4)

Use when proving "if $P$ then $Q$" and you can reason forward from $P$ to $Q$.

Skeleton: Assume $P$. Unpack definitions. Reason step by step. Arrive at $Q$. $\blacksquare$

Example: If $n$ is even, then $n^2$ is even. (Write $n = 2k$, so $n^2 = 2(2k^2)$.)

Proof by contraposition (Chapter 4)

Use when "if $P$ then $Q$" is awkward forward, but "if $\neg Q$ then $\neg P$" is easy. The two are logically equivalent.

Skeleton: Assume $\neg Q$. Reason to $\neg P$. Conclude $P \rightarrow Q$. $\blacksquare$

Example: If $n^2$ is even, then $n$ is even. (Contrapositive: if $n$ is odd, $n^2$ is odd.)

Proof by contradiction (Chapter 5)

Use when assuming the statement is false yields an absurdity. Powerful for impossibility and non-existence.

Skeleton: Suppose, for contradiction, that the statement is false. Derive a contradiction (something and its negation). Conclude the statement is true. $\blacksquare$

Examples: $\sqrt{2}$ is irrational; there are infinitely many primes; (later) the halting problem is undecidable.

Proof by cases (Chapter 5)

Use when the situation splits into finitely many exhaustive cases.

Skeleton: Show the cases cover all possibilities. Prove the claim in each case. $\blacksquare$ Tip: "without loss of generality" (WLOG) collapses symmetric cases — justify the symmetry.

Example: $\lvert x \rvert \cdot \lvert y \rvert = \lvert xy \rvert$ (cases on the signs of $x,y$).

Mathematical induction (Chapter 6)

Use when proving $P(n)$ for all integers $n \ge n_0$, and $P(k+1)$ builds on $P(k)$.

Skeleton: 1. State $P(n)$. 2. Base case: prove $P(n_0)$. 3. Inductive step: assume $P(k)$ (the inductive hypothesis); prove $P(k+1)$. 4. Conclude $P(n)$ for all $n \ge n_0$. $\blacksquare$

Engines: summations — peel off the last term, then apply the hypothesis; divisibility — unpack "$d \mid x$" as "$x = dm$", do algebra, repackage.

Example: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Strong induction (Chapter 7)

Use when proving $P(k+1)$ needs several (or all) previous cases, not just $P(k)$ — typical for divide-and-conquer and prime factorization.

Skeleton: Assume $P(j)$ for all $n_0 \le j \le k$; prove $P(k+1)$. (Base case(s) as needed.)

Example: every integer $n \ge 2$ has a prime factorization; correctness of exponentiation by squaring.

Structural induction (Chapter 7)

Use when the objects are recursively defined (sequences, trees, well-formed formulas, lists).

Skeleton: Prove the claim for the base constructor(s); assume it for the components, prove it for each combining constructor. $\blacksquare$

Example: every binary tree with $n$ internal nodes has $n+1$ leaves.

Existence and uniqueness (Chapter 5)

  • Existence (constructive): exhibit a specific object that works.
  • Existence (non-constructive): prove one must exist without building it (e.g., pigeonhole).
  • Uniqueness: assume two objects $x, y$ both work; prove $x = y$.

Disproof by counterexample (Chapter 5)

Use when a universal claim "$\forall x\, P(x)$" is false. A single $x$ with $\neg P(x)$ settles it. (One counterexample disproves; no number of examples proves — that needs a proof.)

Example: "every odd number is prime" is disproved by $9$.

Common failure modes (see Chapter 6)

  • A false or missing base case — a valid step proves nothing without one.
  • An inductive step that secretly needs large $k$ (the "all horses same color" trap).
  • Affirming the consequent and other invalid inferences (Chapter 3).
  • Assuming what you're proving — but note: assuming $P(k)$ to prove $P(k+1)$ is not this; it's a valid implication.
  • Proving the converse ($Q \rightarrow P$) when you meant $P \rightarrow Q$.