1. What a proof is
A finite sequence of statements $\varphi_1, \varphi_2, \ldots, \varphi_n$ where each $\varphi_i$ is an axiom, a previously proved theorem, or follows from earlier statements by an inference rule. The last statement $\varphi_n$ is the theorem being proved.
That's the formal definition. In practice, a working proof is a piece of writing that lets a competent reader reconstruct such a sequence — not necessarily the sequence itself, but enough scaffolding that they could fill in every step if they wanted to.
A proof technique is a reusable architectural pattern for assembling that scaffolding. The techniques in this page aren't different kinds of logic — they all rest on the same inference machinery from propositional and predicate logic. What changes is the strategy: where you start, what you assume, and what shape the conclusion takes.
When a reader sees "Assume $\sqrt{2} = p/q$" they instantly orient: this is a contradiction proof. The explicit strategy declaration is a courtesy to the reader — and a discipline for the writer, because it forces you to know what shape your argument is supposed to have before you start.
2. Picking the right technique
The choice of technique is mostly driven by the logical form of the statement. Read the statement, identify the form, and the technique is usually obvious.
| Statement form | First-choice technique | Why |
|---|---|---|
| $P \to Q$ | Direct | Assume $P$, derive $Q$. Default. |
| $P \to Q$ where $\neg Q$ is easier to manipulate | Contrapositive | $P \to Q \equiv \neg Q \to \neg P$. Trade the assumption. |
| $P$ where $\neg P$ unlocks structure | Contradiction | Assume $\neg P$, find an explicit inconsistency. |
| Statement involves cases (parity, sign, trichotomy) | Cases | Partition the domain, handle each. |
| $\forall n \in \mathbb{N}, P(n)$ | Induction | Reduce an infinite claim to a base case and a step. |
| $\exists x, P(x)$ | Construction | Exhibit a specific $x$ and verify $P(x)$. |
| $\neg \forall x, P(x)$ | Counterexample | Exhibit one $x$ with $\neg P(x)$. |
| Finite, enumerable domain | Exhaustion | Check every case mechanically. |
These are first choices, not rules. Many theorems can be proved several ways, and the elegance of a proof often depends on choosing the technique that matches the underlying structure rather than the surface form.
3. Direct proof
The default move for proving $P \to Q$. Assume $P$. Unfold its definition into something concrete you can manipulate. Apply algebra, prior theorems, or inference rules to push the assumption toward $Q$. Stop when you've written $Q$.
The logical structure is the implication introduction rule: if from assumption $P$ you can derive $Q$, then you have proved $P \to Q$. The proof is that derivation.
Let $a$ and $b$ be even integers. By definition of "even," there exist integers $m$ and $n$ with $a = 2m$ and $b = 2n$.
Then
$$ a + b = 2m + 2n = 2(m + n). $$Since $m + n$ is an integer, $a + b$ has the form $2 \cdot (\text{integer})$, which is the definition of even.∎
Notice the rhythm: definition in, algebra in the middle, definition out. Direct proofs almost always have this shape. The hard part is rarely the algebra — it's spotting that the definitions on both ends need to be unpacked.
4. Proof by contrapositive
Still proving $P \to Q$, but from the other end. Instead of assuming $P$ and chasing $Q$, you assume $\neg Q$ and chase $\neg P$. The result is logically the same statement, because
$$ P \to Q \;\equiv\; \neg Q \to \neg P. $$This equivalence is a theorem of classical propositional logic (check it with a truth table). The two implications are true together and false together — proving either one proves both.
Reach for the contrapositive whenever $\neg Q$ is a more concrete, manipulable statement than $Q$. A common signal: $Q$ has the form "$X$ is even" or "$X$ is rational" — a property that's hard to use directly, but whose negation ("$X$ is odd" or "$X$ is irrational") plugs straight into algebra.
We prove the contrapositive: if $n$ is odd, then $n^2$ is odd.
Suppose $n$ is odd. Then $n = 2k + 1$ for some integer $k$. Squaring,
$$ n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1. $$Since $2k^2 + 2k$ is an integer, $n^2$ has the form $2 \cdot (\text{integer}) + 1$, which is odd.
By contraposition, if $n^2$ is even then $n$ is even.∎
The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ — equivalent. The converse is $Q \to P$ — not equivalent. "If it's raining then the ground is wet" does not entail "if the ground is wet then it's raining." Proving the converse proves a different theorem.
5. Proof by contradiction
To prove $P$, assume $\neg P$ instead. Derive a contradiction — any statement and its negation, both true at once. Conclude that $\neg P$ was untenable, hence $P$.
The validity rests on the law of excluded middle: classically, either $P$ or $\neg P$ holds. If $\neg P$ leads to nonsense, $P$ must be the case. (Intuitionistic logic rejects this move for arbitrary $P$; see the note at the end.)
Contradiction is the technique of choice when the negation of the conclusion gives you a strong, manipulable hypothesis. "$\sqrt{2}$ is irrational" is hard to use; "$\sqrt{2} = p/q$" is something you can square.
Suppose for contradiction that $\sqrt{2}$ is rational. Then there exist integers $p$ and $q$, with $q \neq 0$ and $\gcd(p, q) = 1$ (the fraction is in lowest terms), such that
$$ \sqrt{2} = \frac{p}{q}. $$Squaring both sides and clearing the denominator,
$$ 2q^2 = p^2. $$So $p^2$ is even. By the contrapositive theorem of the previous section, $p$ itself is even. Write $p = 2r$. Substituting,
$$ 2q^2 = (2r)^2 = 4r^2 \quad\Longrightarrow\quad q^2 = 2r^2. $$So $q^2$ is even, hence $q$ is even. But then $p$ and $q$ share the factor $2$, contradicting $\gcd(p, q) = 1$.
The assumption that $\sqrt{2}$ is rational is untenable, so $\sqrt{2}$ is irrational.∎
You must derive a contradiction that uses the assumption $\neg P$. Deriving a random falsehood from side hypotheses doesn't prove anything about $P$. The contradiction's logical content has to trace back to the negation you introduced.
6. Proof by cases
Partition the domain into mutually exclusive, jointly exhaustive subcases. Prove the claim in each. Conclude it holds throughout.
The logical structure is disjunction elimination: if $A \vee B$ holds, and $A \to P$ and $B \to P$ both hold, then $P$ holds. The "$A \vee B$" is your partition; the two implications are the per-case arguments.
Cases is the right technique whenever the natural argument splits — most often on parity, sign, or the trichotomy $x < 0$, $x = 0$, $x > 0$. State the partition explicitly so the reader can check it really is exhaustive.
Every integer is either even or odd. We consider both cases.
Case 1: $n$ is even. Write $n = 2k$. Then
$$ n^2 + n = 4k^2 + 2k = 2(2k^2 + k), $$which is even.
Case 2: $n$ is odd. Write $n = 2k + 1$. Then
$$ n^2 + n = (2k+1)^2 + (2k+1) = (2k+1)\big((2k+1) + 1\big) = (2k+1)(2k+2) = 2(2k+1)(k+1), $$which is even.
In every case, $n^2 + n$ is even, and the two cases cover all integers.∎
7. Mathematical induction (weak)
Induction proves a statement of the form $\forall n \in \mathbb{N}, P(n)$ — infinitely many statements at once — by reducing it to two finite tasks:
- Base case. Prove $P(0)$ (or $P(1)$, depending on where the claim starts).
- Inductive step. Prove $P(k) \to P(k+1)$ for an arbitrary natural number $k$.
From these two facts, the induction principle concludes $\forall n, P(n)$. The principle is itself an axiom (or a consequence of the well-ordering of $\mathbb{N}$, depending on your foundations): if $P$ holds at the start and propagates by one step at a time, it must hold everywhere along the chain.
The image is a row of dominoes. The base case tips the first one. The inductive step is the guarantee that each domino knocks the next one over. Together they topple the whole row.
Inside the inductive step you are allowed to assume $P(k)$ — this is the inductive hypothesis. You use it to prove $P(k+1)$. A "proof by induction" that derives $P(k+1)$ without ever using the hypothesis is not really an induction; it's a direct proof of $P$ for every $n$, which is fine if it works, but it doesn't use the induction machinery.
Base case ($n = 1$). The left side is $1$. The right side is $\dfrac{1 \cdot 2}{2} = 1$. They agree.
Inductive step. Fix an arbitrary $k \geq 1$ and assume the inductive hypothesis
$$ \sum_{i=1}^{k} i = \frac{k(k+1)}{2}. $$We must prove the statement for $k + 1$, namely that $\displaystyle\sum_{i=1}^{k+1} i = \dfrac{(k+1)(k+2)}{2}$.
Compute, splitting off the last term and applying the hypothesis:
$$ \begin{aligned} \sum_{i=1}^{k+1} i &= \left(\sum_{i=1}^{k} i\right) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \\ &= \frac{k(k+1) + 2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2}. \end{aligned} $$This is exactly the claim at $k + 1$.
By induction, the formula holds for every $n \geq 1$.∎
Arrange $1 + 2 + \cdots + n$ as a staircase of dots; copy it, flip the copy, and slot the two together. You get an $n \times (n+1)$ rectangle containing $2 \cdot (1 + 2 + \cdots + n)$ dots, so the sum is $n(n+1)/2$. The induction proof formalises what this picture shows in a glance.
8. Strong induction
Sometimes proving $P(k+1)$ requires assuming not just $P(k)$ but several earlier cases — perhaps all of $P(0), P(1), \ldots, P(k)$. The fix is to strengthen the inductive hypothesis: assume $P(j)$ for every $j \leq k$, and prove $P(k+1)$.
This is strong induction. It looks like a stronger principle than weak induction, but it isn't — the two are logically equivalent, and either can be derived from the other (and both from the well-ordering of $\mathbb{N}$). Strong induction is just a packaging choice that's clearer when the inductive step needs to reach back further than one step.
Base case ($n = 2$). $2$ is itself prime, so it is a product of one prime (itself).
Inductive step. Fix $k \geq 2$ and assume that every integer $j$ with $2 \leq j \leq k$ is a product of primes. We prove the claim for $k + 1$.
If $k + 1$ is prime, it is a product of one prime (itself) and we are done.
Otherwise $k + 1$ is composite, so $k + 1 = a \cdot b$ for some integers $a, b$ with $2 \leq a, b \leq k$. By the inductive hypothesis applied to $a$ and to $b$, each is a product of primes. Concatenating those two products gives a product of primes equal to $k + 1$.
By strong induction, every integer $n \geq 2$ is a product of primes.∎
Notice why weak induction would be awkward here: the factors $a$ and $b$ can be anywhere in $[2, k]$, not specifically at $k$. Strong induction matches the structure of the argument.
9. Exhaustion and construction
Two more techniques worth naming, both of which are really special cases of the patterns above.
Proof by exhaustion
Proof by exhaustion is proof by cases pushed to its mechanical limit: when the domain is finite (or finitely partitionable into manageable subcases), you check every one. The four-colour theorem is the canonical example — its proof reduces the problem to a finite (very large) list of configurations and verifies each by computer. Less dramatically, proving a property of all $2 \times 2$ Boolean functions by writing out all $16$ truth tables is exhaustion.
The technique is sound whenever the case list really is exhaustive and each case really is checked. It tends to feel unsatisfying — there's no insight, just verification — but a valid proof is a valid proof.
Proof by construction
Proof by construction (or constructive existence proof) is the standard way to prove $\exists x, P(x)$: exhibit a specific $x$ and verify that $P(x)$ holds. "There exists a rational number between $\frac{1}{3}$ and $\frac{1}{2}$" is proved by writing down $\frac{2}{5}$ and checking.
The opposite move is non-constructive existence: prove $\exists x, P(x)$ without producing the witness. Pigeonhole arguments, fixed-point theorems, and proofs by contradiction of existence claims all do this. The pigeonhole principle tells you that among 13 people some two share a birth month — but the proof doesn't tell you which two. Both kinds of existence proof are valid in classical logic; constructive logic accepts only the first.
Classical mathematics accepts the law of excluded middle ($P \vee \neg P$) and freely uses proof by contradiction even for existence statements. Intuitionistic or constructive mathematics rejects this: a proof of $\exists x, P(x)$ must produce $x$, and $\neg\neg P$ does not by itself imply $P$. Most of mainstream mathematics is classical, but constructive proofs carry extra information (the witness) and matter in computer science, where "exists" usually has to mean "computable."
10. Common pitfalls
The contrapositive of $P \to Q$ is $\neg Q \to \neg P$ (equivalent). The converse is $Q \to P$ (not equivalent). Mixing them up doesn't just give a worse proof; it gives a proof of the wrong theorem.
If your "inductive step" derives $P(k+1)$ without referring to $P(k)$, you haven't done an induction — you've done a direct proof in disguise. That's sometimes fine, but more often the direct argument doesn't actually work, and you're papering over a gap.
If the claim is $\forall n \geq 1, P(n)$, the base case is $P(1)$, not $P(0)$. Get this wrong and the entire chain starts one rung up from where it needed to.
A famous fake "proof" by induction that all horses in any group are the same colour fails because the inductive step from $n=1$ to $n=2$ has no overlap — two single-horse groups share no horse to anchor the comparison. The lesson: always verify the inductive step works from the base case to the next case, not just for large $n$. Small-$n$ pathology is where bad inductions hide.
Circular reasoning — assuming the conclusion, sometimes unconsciously, after a clever rearrangement. Particularly easy in proofs by contradiction, where the negation can be manipulated into something that looks like a step toward the conclusion. Be ruthless about which statements come from where.
$P \to Q$ is automatically true whenever $P$ is false (the conditional is "vacuously true"). If you find yourself proving an implication by showing the hypothesis is never satisfied, double-check that the theorem actually means what you think it means.