Proof Techniques

Proving Versus Implementing

A working program is evidence, not proof. It shows the code did the right thing on the inputs you tried. A proof shows a claim holds for every case at once. A mathematical proof is “a deductive argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion.” The moment a course or a correctness argument asks why an algorithm works rather than that it ran, you need one of a small set of standard strategies.

Note

The payload: the shape of the statement selects the technique. An implication chooses between direct proof and contrapositive; a universal claim invites contradiction; a “for all cases” claim splits into cases; and a single well-chosen counterexample destroys a universal claim outright. Reading the logical form of what you must prove is most of the work.

The Toolkit

Technique	Best for	Move
Direct proof	$p\to q$ with a clear forward path	Assume $p$, derive $q$
Contrapositive	$p\to q$ where $\neg q$ is easier to work with	Prove $\neg q\to \neg p$ instead
Contradiction	Existence/impossibility, irrationality	Assume the negation, derive an absurdity
Proof by cases	Claims that split on a finite partition	Prove each case separately
Counterexample	Disproving a universal claim	Exhibit one instance that fails

Direct proof

The default. The conclusion “is established by logically combining the axioms, definitions, and earlier theorems.” You assume the hypothesis and chain known facts forward until the conclusion drops out. Proving “if $n$ is even then $n^2$ is even” by writing $n=2k$ and computing $n^2=2(2k^2)$ is a direct proof.

Contrapositive

An implication and its contrapositive are logically equivalent, so proving one proves the other. This technique “infers the statement ‘if p then q’ by establishing the logically equivalent contrapositive statement: ‘if not q then not p’.” Reach for it when the negated conclusion gives you something concrete to manipulate. To show “if $n^2$ is even then $n$ is even,” the direct route stalls, but the contrapositive “if $n$ is odd then $n^2$ is odd” is a one-line direct proof.

Proof by contradiction

Also called reductio ad absurdum. You show that “if some statement is assumed true, a logical contradiction occurs, hence the statement must be false.” Assume the opposite of what you want, follow the consequences, and hit an impossibility. The archetype is the irrationality of $\sqrt{2}$: assume $\sqrt{2}=a/b$ in lowest terms, derive that $a$ and $b$ are both even, and that contradicts “lowest terms.”

Proof by cases

When the domain splits into finitely many situations, “the conclusion is established by dividing it into a finite number of cases and proving each one separately.” Also called proof by exhaustion. The obligation is completeness: the cases must cover every possibility with no gap. A proof that $n(n+1)$ is always even splits on the parity of $n$, and the two cases together cover all integers.

Counterexample

To disprove a universal claim you do not need a general argument, only one failure. A single instance can “construct a counterexample to disprove a proposition that all elements have a certain property.” “Every prime is odd” dies to $n=2$. This is the constructive twin of quantifier negation: refuting $\forall xP(x)$ means producing an $x$ with $\neg P(x)$, so a counterexample is that witness made explicit.

Example

One claim, two failed tools, one that works. Prove: for integers, if $n^2$ is odd then $n$ is odd.

Direct stalls: from $n^2=2k+1$ there is no clean handle on $n$.

Contradiction works but is heavier: assume $n^2$ odd and $n$ even, write $n=2m$, get $n^2=4m^2$ (even), contradiction.

Contrapositive is cleanest: prove “if $n$ is even then $n^2$ is even,” which is $n=2m\Rightarrow n^2=2(2m^2)$. Done in one line. Picking the technique that matches the statement’s shape saved the most work.

Tip

For statements about all natural numbers with a recursive or cumulative structure, none of these is the right first tool. That is the job of induction, which deserves its own treatment.

Related Notes

• Mathematical Induction - the technique for “for all n” statements over the naturals
• Propositional Logic - equivalences like contraposition come straight from truth tables
• Predicate Logic and Quantifiers - the quantifier shape of a claim tells you which proof to try
• Recursion - correctness of recursive code is typically an inductive proof

Sources

• Mathematical proof (Wikipedia) - definitions of direct proof, contraposition, proof by exhaustion, and counterexample.
• Proof by contradiction (Wikipedia) - the reductio structure and the square-root-of-two example.