Target Audience: Anyone ready to write proofs, not just read them.
Prerequisites: Logic and Quantifiers — every technique here is one of that page's equivalences turned into a method.
The previous page settled what statements mean. This one is about what to actually write on the paper. Each technique gets the same treatment: the logical equivalence that licenses it, a reusable template, a worked example, and the sign that tells you to reach for it.
Sections 2–7 are the methods for proving a single statement; 8 and 9 are for proving infinitely many at once, and are where most people's first real difficulty lies. Work the induction explorer until the inductive step stops feeling like circular reasoning — that misunderstanding is the single most common obstacle, and Section 10 addresses it head on.
Every technique on this page is used by a proof already on this site; each section links to the one that shows it working at full length.
A proof of a statement is a finite sequence of statements, ending with the one to be proved, in which every statement is either a hypothesis, a definition, a previously established result, or follows from earlier statements by a rule of inference.
Nothing in that definition mentions persuasion. A proof is not an argument that convinces a reader; it is a chain each of whose links can be checked in isolation. If every link holds, the conclusion holds whether anyone is convinced or not.
Most theorems are conditionals, \(P \Rightarrow Q\), usually with a hidden universal quantifier in front: "if \(n\) is even then \(n^2\) is even" means "for every integer \(n\)…". So the basic task is: given that \(P\) holds for an arbitrary object, establish \(Q\) for that same object. The techniques in Sections 2–4 are three different routes to exactly that, and each is justified by an equivalence from the previous page:
| Technique | What you actually prove | Why that suffices |
|---|---|---|
| Direct | Assume \(P\), derive \(Q\) | This is the definition of establishing \(P \Rightarrow Q\) |
| Contrapositive | Assume \(\lnot Q\), derive \(\lnot P\) | \((P \Rightarrow Q) \equiv (\lnot Q \Rightarrow \lnot P)\) |
| Contradiction | Assume \(P \land \lnot Q\), derive an absurdity | \(\lnot(P \Rightarrow Q) \equiv P \land \lnot Q\); if that is impossible, the conditional holds |
Read that table again after Section 4. It is the whole logical content of this page; the rest is craft.
Almost every worked example below turns on one of these definitions. They look trivial, and they are exactly what makes the algebra go through.
The move that starts most proofs is replacing a word by its definition — turning "\(n\) is even" into the usable object \(2k\).
The default. Assume the hypothesis, unpack the definitions, do the algebra, arrive at the conclusion. Reach for something else only when the hypothesis turns out to be hard to work with.
Proof. Assume \(P\).
[Replace the words in \(P\) by their definitions; work forward.]
Therefore \(Q\). \(\blacksquare\)
Claim. If \(n\) is even, then \(n^2\) is even.
Proof. Assume \(n\) is even. By definition \(n = 2k\) for some integer \(k\). Then
Since \(2k^2\) is an integer, \(n^2\) has the form \(2m\), so \(n^2\) is even. \(\blacksquare\)
Every step is a definition or algebra. Note the last line: it is not enough to reach \(4k^2\) — you must exhibit the form the conclusion's definition demands.
Writing "\(n^2\) is even, so \(n^2 = 2m\)…" begins by assuming what you are proving. A direct proof starts at \(P\) and moves toward \(Q\), never the reverse. See Section 10.
To prove \(P \Rightarrow Q\), prove \(\lnot Q \Rightarrow \lnot P\) instead. The two are logically equivalent, so a proof of either is a proof of both. This is a direct proof — of a different statement.
Proof. We prove the contrapositive: assume \(\lnot Q\).
[Work forward from \(\lnot Q\).]
Therefore \(\lnot P\), which proves \(P \Rightarrow Q\). \(\blacksquare\)
Claim. If \(n^2\) is even, then \(n\) is even.
A direct attempt stalls immediately: "\(n^2\) is even" gives \(n^2 = 2k\), and there is nothing useful to do with a square root. The contrapositive gives a usable hypothesis instead.
Proof. We prove the contrapositive: if \(n\) is odd, then \(n^2\) is odd. Assume \(n\) is odd, so \(n = 2k+1\). Then
which is odd. Therefore if \(n^2\) is even, \(n\) is even. \(\blacksquare\)
When \(\lnot Q\) is more usable than \(P\). "\(n\) is odd" hands you the explicit form \(2k+1\); "\(n^2\) is even" hands you almost nothing about \(n\). Negations of "not", "no", "irrational", and "at most" are often concrete in exactly this way.
This example is not a toy: it is the step the Irrationality of √2 proof leans on twice, and its "Technique check" remark makes the same point.
Assume the statement is false, and derive something impossible. Since a false assumption is the only thing that could have produced an impossibility, the statement must be true.
For a conditional, the negation is not another conditional. From the previous page, \(\lnot(P \Rightarrow Q) \equiv P \land \lnot Q\). So to prove \(P \Rightarrow Q\) by contradiction you assume both \(P\) and \(\lnot Q\), and derive an absurdity. For a bare statement \(S\), you assume \(\lnot S\).
Getting this negation wrong is the commonest way a contradiction proof goes astray before it starts — which is why negation was given a section of its own.
Proof. Suppose, for contradiction, that \(P\) holds and \(Q\) fails.
[Derive two statements that cannot both be true.]
This is impossible, so the supposition fails and \(P \Rightarrow Q\). \(\blacksquare\)
\(\sqrt{2}\) is irrational. Suppose not: \(\sqrt{2} = a/b\) in lowest terms. Then \(a^2 = 2b^2\), so \(a^2\) is even, so \(a\) is even by Section 3 — write \(a = 2c\). Then \(4c^2 = 2b^2\), so \(b^2 = 2c^2\) and \(b\) is even too. But then \(a\) and \(b\) share the factor \(2\), contradicting "lowest terms". Full argument: The Irrationality of √2, generalised on The Irrationality of √p for Every Prime p.
There are infinitely many primes. Suppose the primes are exactly \(p_1, \ldots, p_n\). Consider \(N = p_1 p_2 \cdots p_n + 1\). No \(p_i\) divides \(N\) (each leaves remainder \(1\)), yet \(N \geq 2\) has a prime divisor — which is therefore not on the list. Contradiction. Full argument: The Infinitude of Primes.
The second proof quietly uses "every integer \(\geq 2\) has a prime divisor" — itself proved by strong induction on Every Integer ≥ 2 Has a Prime Divisor, and the subject of Section 9.
If your "contradiction" proof assumes \(P\) and \(\lnot Q\), never uses \(P\) again, and derives \(\lnot P\) — you have written a contrapositive proof wrapped in unnecessary packaging. Drop the wrapper; the direct form is shorter and clearer. The Infinitude of Primes page's technique note makes the related observation that its contradiction contains a construction, and so proves something positive directly.
Split the hypothesis into finitely many possibilities, and prove the conclusion in each. The cases must be exhaustive — they may overlap, but nothing may fall between them.
Proof. Every \(x\) falls into at least one of Case 1, …, Case n.
Case 1: […] Therefore \(Q\).
Case n: […] Therefore \(Q\). In every case \(Q\) holds. \(\blacksquare\)
Claim. For every integer \(n\), the number \(n^2 + n\) is even.
Proof. Either \(n\) is even or \(n\) is odd — exhaustive.
Case 1, \(n = 2k\): \(n^2 + n = 4k^2 + 2k = 2(2k^2 + k)\), even.
Case 2, \(n = 2k+1\): \(n^2 + n = (4k^2+4k+1) + (2k+1) = 2(2k^2 + 3k + 1)\), even.
In both cases \(n^2 + n\) is even. \(\blacksquare\)
Cases on "\(x \gt 0\)" and "\(x \lt 0\)" forget \(x = 0\). Cases on sign for a product forget that one factor may vanish. Before writing a word of Case 1, say out loud why every object is covered — boundary values are where the gap hides.
"There is exactly one \(x\) such that \(P(x)\)" — the \(\exists!\) of the previous page — is two claims, and needs two proofs. They are independent: either can hold without the other.
A constructive existence proof builds the object and checks it works. A non-constructive one shows an object must exist without producing one — for example by contradiction, or by a counting argument. The constructive kind is strictly more useful: it hands you the thing.
The Infinitude of Primes argument is the interesting middle case: dressed as a contradiction, it nonetheless constructs a new prime from any finite list.
Uniqueness. Suppose \(x\) and \(y\) both satisfy \(P\).
[Use \(P(x)\) and \(P(y)\) to force them together.]
Then \(x = y\). \(\blacksquare\)
Claim. The equation \(3x + 7 = 1\) has exactly one real solution.
Existence. \(x = -2\) satisfies it: \(3(-2) + 7 = 1\). (Constructive — we produced the solution.)
Uniqueness. Suppose \(3x + 7 = 1\) and \(3y + 7 = 1\). Subtracting, \(3(x - y) = 0\), so \(x = y\). \(\blacksquare\)
The uniqueness half is the pattern used all over this site — most visibly on The Fundamental Theorem of Arithmetic: Uniqueness, where "two factorisations of the same number" are forced to coincide.
Because \((P \Leftrightarrow Q) \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)\), an "if and only if" theorem needs two proofs. Each direction may use whichever technique suits it — they need not match.
(\(\Rightarrow\)) Assume \(P\). […] Therefore \(Q\).
(\(\Leftarrow\)) Assume \(Q\). […] Therefore \(P\). \(\blacksquare\)
Claim. An integer \(n\) is even if and only if \(n^2\) is even.
(\(\Rightarrow\)) Direct, from Section 2. (\(\Leftarrow\)) Contrapositive, from Section 3. Two directions, two different techniques, one theorem. \(\blacksquare\)
Some biconditionals can be proved as a chain of equivalences, \(P \Leftrightarrow R \Leftrightarrow S \Leftrightarrow Q\) — but only if every link is genuinely reversible. Squaring both sides is not reversible; neither is multiplying by a quantity that might be zero. A single one-way step silently reduces the chain to a proof of one direction. Writing the two directions separately is the safer habit.
The techniques so far prove one statement. Induction proves infinitely many — \(P(n)\) for every integer \(n \geq n_0\) — with two finite pieces of work.
Let \(P(n)\) be a statement about integers \(n \geq n_0\). If
then \(P(n)\) is true for every \(n \geq n_0\).
The statement \(P(k)\) assumed in the step is the inductive hypothesis. Note what step 2 asks for: not that \(P(k)\) is true, but that if it is, so is \(P(k+1)\) — a conditional, proved for an arbitrary \(k\).
Proof. By induction on \(n\).
Base case. \(n = n_0\): [verify \(P(n_0)\) directly].
Inductive step. Let \(k \geq n_0\) and assume \(P(k)\). [Derive \(P(k+1)\), using \(P(k)\) somewhere.] Therefore \(P(k+1)\).
By induction, \(P(n)\) holds for all \(n \geq n_0\). \(\blacksquare\)
Claim. \(1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}\) for every \(n \geq 1\).
Base case. \(n = 1\): the left side is \(1\), the right is \(\frac{1 \cdot 2}{2} = 1\). True.
Inductive step. Assume \(1 + \cdots + k = \frac{k(k+1)}{2}\). Add \(k+1\) to both sides:
which is the claim at \(k+1\). By induction it holds for all \(n \geq 1\). \(\blacksquare\)
The full page, with a second non-inductive proof by pairing: Proof by Induction: The Gauss Sum.
Pick a statement and a value of \(k\). The explorer checks the base case, then shows the three lines an inductive step actually writes: what \(P(k)\) lets you assume, what gets added, and that the result is exactly \(P(k+1)\). Every number is computed live.
| n | left side | right side | status |
|---|
The highlighted row is the \(k\) you chose. An induction proof does the first row by hand and the arrow between consecutive rows once, in general — never the whole table.
The inductive step looks like it assumes what is being proved. It does not. It proves the conditional \(P(k) \Rightarrow P(k+1)\) — and a conditional says nothing about whether its hypothesis is true. The base case is what supplies a true hypothesis to start from; the step then propagates it. Remove the base case and the steps still hold while nothing is ever proved: "\(1 + \cdots + n = \frac{n(n+1)}{2} + 7\)" has a perfectly valid inductive step and is false for every \(n\).
Try it in the explorer: the arithmetic of the step never fails for that shifted claim — only the base case does.
If your inductive step reaches \(P(k+1)\) without ever invoking \(P(k)\), you have not written an induction — you have written a direct proof, and the induction scaffolding is noise. Point at the line where the hypothesis was used; if there isn't one, restructure.
Identical to ordinary induction except in what the step may assume: instead of just \(P(k)\), you may assume \(P(n_0), P(n_0+1), \ldots, P(k)\) — all previous cases — and must derive \(P(k+1)\).
The two principles are equivalent: anything provable by one is provable by the other. Strong induction is a convenience, and the right one whenever \(P(k+1)\) depends on a case well below \(k\).
Proof. Strong induction on \(n \geq 2\). Let \(n \geq 2\) and assume every integer \(m\) with \(2 \leq m \lt n\) has a prime divisor.
If \(n\) is prime, \(n\) divides itself and we are done. If not, \(n = ab\) with \(2 \leq a \lt n\). By the inductive hypothesis \(a\) has a prime divisor \(p\); and \(p \mid a\) with \(a \mid n\) gives \(p \mid n\). \(\blacksquare\)
Ordinary induction is useless here: knowing about \(n-1\) says nothing about the factors of \(n\). The full page, and the reason its base case needs no separate check: Every Integer ≥ 2 Has a Prime Divisor.
Every non-empty set of positive integers has a least element. It is equivalent to both forms of induction, and it powers the minimal counterexample technique: assume the set of counterexamples is non-empty, take its smallest member, and derive a contradiction — usually by producing a smaller one.
This is the shape behind The Fundamental Theorem of Arithmetic: Uniqueness (its "minimal-criminal twin" remark) and behind the descent reading of the √2 proof. The uniqueness argument also depends on Euclid's Lemma, which is where its real work is done.
Using \(Q\), or anything equivalent to it, as a step toward proving \(Q\). It often hides inside "clearly" or inside an algebraic manipulation that silently multiplies both sides of the very equation being established.
Checking finitely many cases of a \(\forall\) statement proves nothing — \(n^2 + n + 41\) is prime for \(n = 0, 1, \ldots, 39\) and composite at \(n = 40\). The exception is a genuinely finite domain, where exhaustive checking is proof by cases.
The mirror image is not a fallacy but a duty: to disprove \(\forall x,\, P(x)\) you need exactly one counterexample, because its negation is \(\exists x,\, \lnot P(x)\). One \(n = 40\) settles the claim above.
"Let \(n\) be an even integer, say \(n = 6\)" — the moment you name a value, you are proving one case. Keep the object arbitrary: \(n = 2k\) with \(k\) unspecified.
To start a contradiction proof of \(P \Rightarrow Q\) you assume \(P \land \lnot Q\), not "if \(P\) then not \(Q\)". This is the single most consequential slip on the page, and the reason negation comes before proof technique.
| Technique | The one thing to remember |
|---|---|
| Direct | Replace words by definitions and work forward. The default. |
| Contrapositive | Use it when \(\lnot Q\) is more usable than \(P\). It is a direct proof of an equivalent statement. |
| Contradiction | Assume \(P \land \lnot Q\) — never another conditional. Best for "no such thing exists". |
| Cases | Exhaustive, possibly overlapping. Check the boundary values. |
| Existence / uniqueness | Two independent claims. Uniqueness: assume two, force them equal. |
| Biconditional | Two proofs, one per direction; chains of equivalences only if every step reverses. |
| Induction | Base case plus \(P(k) \Rightarrow P(k+1)\). Use the hypothesis, or it is not an induction. |
| Strong induction | Assume all previous cases. Reach for it when \(P(k+1)\) depends on a case far below \(k\). |
Text used for this page: Hammack, Book of Proof, Chapters 4–10 (free online). Next in this series: Sets, Relations and Functions — the objects these techniques are usually applied to.
An addendum for when you are staring at a statement and do not know where to start. Read the left column as "what the goal looks like".
| If the goal looks like… | Try | Because |
|---|---|---|
| \(P \Rightarrow Q\), and \(P\) gives you something concrete | Direct | Nothing simpler will do the job |
| \(P \Rightarrow Q\), but \(P\) is a dead end and \(\lnot Q\) is concrete | Contrapositive | Equivalent statement, usable hypothesis |
| "There is no …", "… is irrational", "… is infinite" | Contradiction | Assuming the opposite hands you an object to compute with |
| The hypothesis splits naturally (odd/even, sign, \(n \lt 0\) or not) | Cases | Each branch gives a concrete form |
| "There is exactly one …" | Existence + uniqueness | \(\exists!\) is two claims |
| "… if and only if …" | Both directions | \((P \Leftrightarrow Q) \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)\) |
| "For every integer \(n \geq n_0\) …", especially a sum or a recurrence | Induction | Two finite pieces of work cover infinitely many cases |
| Induction stalls because \(P(k+1)\) needs a case far below \(k\) | Strong induction | Assume every earlier case, not just the last |
| "Every \(n\) has property \(R\)" and you suspect it is false | One counterexample | \(\lnot\forall x,\, P(x) \equiv \exists x,\, \lnot P(x)\) |
| A smallest offender would lead to a smaller one | Minimal counterexample | Well-ordering forbids an infinite descent |
When two techniques both work, prefer the one that is shorter to read. A contradiction proof that never uses its extra hypothesis should have been a contrapositive; an induction that never uses its hypothesis should have been direct.