Proof Methods: Direct, Contrapositive, Contradiction & Induction

Proof techniques · Updated July 2026

Ask a discrete math student what the hardest part of the course is, and the answer is almost always the same: "I don't know how to start a proof." The secret most textbooks bury is that starting is a selection problem before it is a writing problem. There are only a handful of standard methods, each with recognizable trigger patterns. Learn the triggers and the blank page becomes a menu.

Direct proof: the default

A direct proof of "if P, then Q" assumes P, then marches forward with definitions and algebra until Q appears. It is the method to try first, and it works far more often than nervous students expect.

Model: Claim: if n is even, then n² is even. Assume n is even, so n = 2k for some integer k. Then n² = 4k² = 2(2k²), which is 2 times an integer. So n² is even. ∎

Notice the rhythm: unpack the definition (even means 2k), compute, repack the definition (2 times an integer means even). A large fraction of introductory proofs are exactly this three-beat pattern. When students say they "can't do proofs," they often mean they have not memorized the definitions precisely enough to unpack them — which is fixable.

Contrapositive: when the conclusion is easier to negate

The statement "if P, then Q" is logically equivalent to "if not-Q, then not-P" — you can verify this with a four-row truth table. Proving the contrapositive is proving the original.

Trigger: the hypothesis is awkward but the negated conclusion is friendly. Classic example: "if n² is even, then n is even." Starting from "n² is even" gives you 2k = n² — and now you are stuck taking square roots. Flip it: assume n is odd (not-Q), show n² is odd (not-P). That is a one-line direct proof: (2k+1)² = 2(2k² + 2k) + 1. Odd. Done.

Rule of thumb: when the conclusion talks about a property of a simpler object than the hypothesis does, try the contrapositive.

Contradiction: prove it can't be false

Proof by contradiction assumes the entire claim is false, then derives something impossible — a statement that contradicts an assumption, a known theorem, or itself. Since falsehood leads to absurdity, the claim must be true.

Triggers: claims of impossibility or non-existence ("there is no largest prime," "√2 is irrational"), and claims where negating gives you something concrete to compute with. The famous proof that √2 is irrational starts by assuming √2 = a/b in lowest terms — suddenly you have actual integers to push around, and the push ends with both a and b even, contradicting "lowest terms."

A warning that graders wish more students heard: contradiction is a scalpel, not a default. If your "contradiction proof" assumes not-Q, derives not-P, and declares victory, you actually wrote a contrapositive proof wearing a disguise — and the extra scaffolding just adds places to make mistakes. Reach for contradiction when negation genuinely gives you new material to work with.

Induction: the CS student's power tool

Induction proves that a statement P(n) holds for all integers n ≥ n₀. Two obligations:

1. Base case: verify P(n₀) directly.
2. Inductive step: assume P(k) holds (the inductive hypothesis), and prove P(k+1) follows.

The domino metaphor survives because it is accurate: the base case tips the first domino, the inductive step guarantees each domino knocks over the next. Triggers: "for all integers n ≥ …", formulas involving n (sums, products, inequalities), and claims about recursively defined structures — which is why induction is everywhere in computer science. Proving a loop invariant, bounding a recurrence, or arguing a recursive function correct are all induction arguments in work clothes.

The two mistakes graders see constantly: forgetting the base case entirely, and writing an inductive step that never actually uses the inductive hypothesis. If your P(k) assumption goes unused, either the proof is wrong or induction was never needed.

Strong induction is the variant where you may assume P(m) for all m from the base case up to k, not just P(k) itself. Use it when k+1 decomposes into smaller cases that are not simply k — for example, factoring an integer into primes, where n = ab splits into two much smaller numbers.

Choosing a method: a quick decision guide

And when you are stuck: write out the definitions of every term in the claim, in full, on paper. More proofs are unlocked by careful unpacking than by inspiration.