Proof Techniques and Mathematical Reasoning

The "transition course" — the bridge between computational mathematics and mathematics as argument. A proof is a chain of implications from accepted premises to the claim, and the craft is a small set of templates plus judgment about which to reach for. This page is the working inventory, each with the logical form, a canonical example, and the failure mode.

Direct proof

To show $P \Rightarrow Q$ : assume $P$ , derive $Q$ . Most proofs are direct, and most difficulty is not logic but unwinding definitions — the standard advice "write down what everything means" solves more exercises than any cleverness. Example: the sum of two even integers is even — write $2a + 2b = 2(a+b)$ ; the proof is the definition, twice.

Contrapositive

$P \Rightarrow Q$ is logically identical to $\neg Q \Rightarrow \neg P$ (see propositional logic); prove whichever gives you more to work with. Example: if $n^2$ is even then $n$ is even — direct is awkward, but the contrapositive ( $n$ odd $\Rightarrow n^2$ odd) is one line: $(2k+1)^2 = 2(2k^2 + 2k) + 1$ . Reach for the contrapositive when the conclusion's negation is more concrete than the hypothesis.

Contradiction

Assume the claim is false; derive an absurdity. Two immortal examples:

$\sqrt{2}$ is irrational: suppose $\sqrt{2} = p/q$ in lowest terms; then $p^2 = 2q^2$ forces $p$ even, then $q$ even — contradicting lowest terms.
Infinitely many primes (Euclid): given finitely many, $p_1 p_2 \cdots p_k + 1$ is divisible by none of them, so some prime is missing from the list.

Discipline: contradiction is powerful but overused — a "proof by contradiction" that never actually uses the negated conclusion is a direct or contrapositive proof wearing a disguise, and rewriting it as one is clearer.

Induction, three strengths

To prove $P(n)$ for all $n \ge n_0$ :

Weak induction: prove $P(n_0)$ , and $P(n) \Rightarrow P(n+1)$ . Example: $1 + 2 + \cdots + n = n(n+1)/2$ .
Strong induction: assume $P(k)$ for all $k < n$ when proving $P(n)$ . Needed when the reduction jumps more than one step — e.g., every integer $\ge 2$ has a prime factorization (a composite $n = ab$ reduces to two arbitrary smaller cases, not $n-1$ ).
Structural induction: induct over a recursively defined structure (trees, formulas, lists) — prove the property for base cases and show each constructor preserves it. This is the workhorse of program verification and the reason functional programmers already know how to induct.

Induction failure modes: forgetting the base case (the "all horses are the same color" fallacy hides there — the inductive step silently assumes $n \ge 2$ ), and an inductive hypothesis too weak to push through — the fix, counterintuitively, is strengthening the claim so the hypothesis gives you more.

Epsilon-delta and quantifier games

Analysis proofs are quantifier management: $\lim_{x \to a} f(x) = L$ means for every $\varepsilon > 0$ there exists $\delta > 0$ such that $0 < |x - a| < \delta$ implies $|f(x) - L| < \varepsilon$ . The template: treat $\varepsilon$ as handed to you by an adversary; your job is to construct $\delta$ (usually by working backward from $|f(x) - L|$ and bounding). Quantifier order is everything — swapping "for every $\varepsilon$ there is a $\delta$ " to "there is a $\delta$ for every $\varepsilon$ " is the difference between continuity and uniform continuity, and half the classical subtleties of real analysis are exactly such swaps.

The rest of the toolkit

Cases: partition exhaustively and prove each; state why the cases exhaust.
Existence: construct the witness explicitly, or argue non-constructively (pigeonhole, probabilistic method, intermediate value theorem).
Uniqueness: suppose two objects satisfy the property; show they are equal.
Counterexample: one suffices to kill a universal claim — and hunting for the counterexample is how you discover why a true claim is true.
Biconditionals: prove both directions separately; they usually deserve different techniques.

Fallacies that survive into adulthood

Affirming the consequent ( $P \Rightarrow Q$ and $Q$ , concluding $P$ ); begging the question (assuming the claim mid-proof, often disguised by notation); dividing by an expression that can be zero (the engine of every 1 = 2 "proof"); proving "for arbitrary large $n$ " and claiming "for all $n$ "; and treating a verified pattern as proof — $n^2 + n + 41$ is prime for $n = 0, \ldots, 39$ and fails at 40.