Mathematical Proof Techniques

⚡ Key Takeaways

Mathematical proof is a rigorous, logically valid argument that establishes the truth of a statement beyond any doubt from accepted premises (axioms, definitions, previously proven theorems). The core techniques are direct proof, contrapositive, contradiction, induction, construction, and exhaustion. They apply across all of mathematics, from number theory to geometry. The method matured from Euclid (c. 300 BCE) through modern formal logic.

💡 The Core Insight

A proof transports you from what you are allowed to assume (the hypothesis $P$ ) to what you must show (the conclusion $Q$ ) using only logically guaranteed steps. The art is choosing the form of the journey: go forward from $P$ (direct), flip the implication ( $\neg Q \Rightarrow \neg P$ ), assume the opposite and crash ( $P \wedge \neg Q \Rightarrow \bot$ ), or climb an infinite ladder one rung at a time (induction). The logic never changes — only the route.

DefinitionThe Conditional and Its Relatives

For statements $P$ (hypothesis) and $Q$ (conclusion), the implication $P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false. Three related conditionals are:

1

\quad \text{Converse: } Q \Rightarrow P

Derivation hint: swap hypothesis and conclusion; NOT logically equivalent to the original.

2

\quad \text{Inverse: } \neg P \Rightarrow \neg Q

Derivation hint: negate both parts of the original; also not equivalent.

3

\quad \text{Contrapositive: } \neg Q \Rightarrow \neg P

Derivation hint: negate AND swap; this IS logically equivalent to $P \Rightarrow Q$ . Here $P$ , $Q$ are propositions; $\neg$ is logical negation ("not"); $\Rightarrow$ is "implies"; $\bot$ denotes a contradiction (a statement that is always false).

TheoremLogical Equivalence of Contrapositive

The implication $P \Rightarrow Q$ and its contrapositive $\neg Q \Rightarrow \neg P$ have identical truth values in every case:

4

\quad (P \Rightarrow Q) \;\equiv\; (\neg Q \Rightarrow \neg P)

Derivation hint: build a four-row truth table; the two columns match.

DefinitionUniversal and Existential Statements

A universal statement claims something for all members of a set; an existential statement claims at least one member exists:

5

\quad \forall x \in S,\; P(x) \qquad\text{vs.}\qquad \exists x \in S,\; P(x)

Derivation hint: $\forall$ ("for all") requires a general argument or induction; $\exists$ ("there exists") is proven by exhibiting a witness. Their negations swap the quantifier:

6

\quad \neg\big(\forall x,\, P(x)\big) \;\equiv\; \exists x,\, \neg P(x), \qquad \neg\big(\exists x,\, P(x)\big) \;\equiv\; \forall x,\, \neg P(x)

Derivation hint: to disprove "all swans are white" you need one black swan; to disprove "a unicorn exists" you must check all things.

ProofDirect Proof Is Valid

1. Goal. Prove $P \Rightarrow Q$ . 2. Method. Assume $P$ is true. (If $P$ is false the implication is automatically true, so this case needs no work.) 3. From $P$ , apply definitions, axioms, and known theorems in a chain of valid inferences. 4. Arrive at $Q$ . 5. Since we reached $Q$ whenever $P$ holds, the only case that could falsify $P \Rightarrow Q$ (namely $P$ true, $Q$ false) never occurs. $\blacksquare$

∎

ProofProof by Contrapositive Is Valid

1. Goal. Prove $P \Rightarrow Q$ . 2. By equation $[4]$ , this is logically equivalent to $\neg Q \Rightarrow \neg P$ . 3. Assume $\neg Q$ (the conclusion fails). 4. Derive $\neg P$ by direct reasoning. 5. Having proven the equivalent statement, the original $P \Rightarrow Q$ holds. $\blacksquare$

∎

ProofProof by Contradiction Is Valid

1. Goal. Prove a statement $R$ (which may itself be $P \Rightarrow Q$ ). 2. Assume $\neg R$ alongside all hypotheses. 3. Derive a contradiction $\bot$ (e.g. $0 = 1$ , or a number both even and odd). 4. Since true premises can never yield a falsehood, the added assumption $\neg R$ must be false. 5. Therefore $R$ is true. (When proving $P\Rightarrow Q$ , one assumes $P \wedge \neg Q$ and reaches $\bot$ .) $\blacksquare$

∎

ProofThe Principle of Mathematical Induction

1. Goal. Prove $\forall n \geq n_0,\; P(n)$ for integers $n$ . 2. Base case. Prove $P(n_0)$ directly. 3. Inductive step. Prove the implication $P(k) \Rightarrow P(k+1)$ for arbitrary $k \geq n_0$ . The assumption $P(k)$ is the inductive hypothesis. 4. Conclusion. By the well-ordering of the integers, $P(n)$ holds for all $n \geq n_0$ .

7

\quad \Big[\,P(n_0)\;\wedge\;\big(\forall k \geq n_0,\; P(k)\Rightarrow P(k+1)\big)\Big]\;\Rightarrow\;\forall n \geq n_0,\; P(n)

Derivation hint: the base case lights the first domino; the inductive step guarantees each domino topples the next, so all fall. $\blacksquare$

∎

mathematician · Euclid of Alexandria | c. 325 – c. 265 BCE

Euclid's Elements is the founding document of the axiomatic method. From five geometric postulates and five "common notions", he deduced 465 propositions across thirteen books, each justified by explicit logical steps from what came before. His proof that there are infinitely many primes — assume finitely many, multiply them all and add one, derive a contradiction — remains the textbook model of proof by contradiction over two millennia later. The phrase "Q.E.D." (quod erat demonstrandum, "which was to be demonstrated") descends directly from his closing formula.

🧠 Intuition

Think of each technique as a tool with a natural job:

Direct proof — when a clear chain of cause-and-effect runs from $P$ to $Q$ . Best for algebraic identities and definitional unpacking.
Contrapositive — when assuming $\neg Q$ gives you something concrete to manipulate but assuming $P$ gives a vague existence claim. ("If $n^2$ is even then $n$ is even" is awkward forward but easy backward: assume $n$ odd, square it, get odd.)
Contradiction — when the statement asserts something is impossible or unique (" $\sqrt 2$ is irrational", "there is no largest prime"). You give your opponent what they want and watch it self-destruct.
Induction — when a statement is indexed by the natural numbers and each case builds on the previous one (sums, divisibility, inequalities for all $n$ ).
Construction — for existence claims: don't argue that a thing exists, build it.
Exhaustion (cases) — when finitely many situations cover everything; check each.

Figure

Decision flowchart for selecting a proof technique

ExampleIrrationality of √2 — Proof by Contradiction

Claim. $\sqrt 2$ is irrational (cannot be written $a/b$ with integers $a,b$ ).

Given / assume the opposite. Suppose $\sqrt 2 = a/b$ in lowest terms, so $a,b$ are integers with no common factor and $b \neq 0$ .

Steps. 1. Square: $2 = a^2/b^2$ , hence $a^2 = 2b^2$ . 2. So $a^2$ is even, which forces $a$ even (contrapositive: odd² is odd). Write $a = 2m$ . 3. Substitute: $(2m)^2 = 2b^2 \Rightarrow 4m^2 = 2b^2 \Rightarrow b^2 = 2m^2$ . 4. So $b^2$ is even, hence $b$ is even. 5. But then $a$ and $b$ share the factor $2$ — contradicting "lowest terms".

Boxed answer.

\boxed{\sqrt 2 \text{ is irrational} \quad(\text{no such } a/b \text{ exists})}

ExampleSum of First n Integers — Proof by Induction

Claim. For all integers $n \geq 1$ :

8

\quad \sum_{i=1}^{n} i \;=\; \frac{n(n+1)}{2}

Derivation hint: base case $n=1$ gives $1=1$ ; inductive step adds $(k+1)$ to both sides.

Given. Prove the formula for every $n \ge 1$ .

Steps. 1. Base case $n=1$ : left side $=1$ ; right side $=\dfrac{1\cdot 2}{2}=1$ . ✓ 2. Inductive hypothesis. Assume $\displaystyle\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$ for some $k \ge 1$ . 3. Inductive step. Add $(k+1)$ :

\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.

4. This is exactly the formula with $n = k+1$ . 5. By induction, the formula holds for all $n \ge 1$ .

Boxed answer (check $n=100$ ).

\boxed{\;\sum_{i=1}^{100} i = \frac{100\cdot 101}{2} = 5050\;}

⚠️ A proof of the converse is NOT a proof of the original

Proving $Q \Rightarrow P$ tells you nothing about $P \Rightarrow Q$ (equation $[1]$ ). "If it rained, the ground is wet" is not established by "if the ground is wet, it rained" — a sprinkler wets the ground. Likewise, one example is never a proof of a universal statement, and a picture is not a proof (it can suggest but cannot guarantee). Finally, in contradiction proofs you must reach a genuine logical impossibility, not merely something surprising.

CounterexampleDisproving "every odd number is prime"

The statement $\forall n\ (n \text{ odd} \Rightarrow n \text{ prime})$ is false. By equation $[6]$ , one counterexample suffices: $n = 9$ is odd but $9 = 3 \times 3$ is composite. A single witness destroys a universal claim — this is the asymmetry between proving "for all" (needs a general argument) and disproving it (needs one case).

⚠️ The flawed-induction trap: "all horses are the same colour"

A famous fallacy "proves" all horses share one colour by induction on the number of horses, failing only because the inductive step silently assumes overlap between two sub-groups that does not exist when $k=1$ . Moral: the inductive step $P(k)\Rightarrow P(k+1)$ must hold for every $k \ge n_0$ , including the smallest. Always check that the step's reasoning is valid right from the base case.

connection

Proof techniques are the connective tissue of mathematics. Mathematical Induction is the engine behind nearly every formula indexed by $n$ and underlies Recursion in computer science. Proof by Contradiction depends on Propositional Logic and the law of the excluded middle, linking proof to the foundations of Set Theory. The structure of Quantifiers dictates whether you build a witness (Constructive Proof) or argue abstractly. The deductive method itself was systematised in Euclidean Geometry and is formalised by First-Order Logic and Truth Tables.

🔬 Where this appears

⏳ History

- c. 600 BCE — Thales of Miletus is credited with the first deductive proofs in geometry, moving beyond empirical measurement.

- c. 300 BCE — Euclid's Elements codifies the axiomatic-deductive method; the infinitude-of-primes proof by contradiction appears.

- c. 250 BCE — Archimedes uses the method of exhaustion, an early limiting/case argument, to compute areas and the value of

\pi

.

- 1654 — Pascal articulates a clear principle of mathematical induction in his treatise on the arithmetic triangle.

- 1847 — George Boole's Mathematical Analysis of Logic turns logical inference into algebra, the seed of Truth Tables.

- 1879 — Gottlob Frege's Begriffsschrift introduces formal quantifier logic, making "for all" and "there exists" precise.

- 1889 — Giuseppe Peano states his axioms for the natural numbers, putting induction on a rigorous footing.

- 1931 — Kurt Gödel proves the incompleteness theorems: any consistent system rich enough for arithmetic contains true statements it cannot prove.

- 1976 — Appel and Haken prove the Four Colour Theorem by computer-assisted exhaustion of 1,936 cases, igniting debate over what counts as a proof.

open-problem

What is a "proof", really? Gödel showed no single axiomatic system can prove all truths about arithmetic, so the notion of "provable" is system-relative. The 1976 Four Colour Theorem and the 1998 Hales proof of the Kepler conjecture relied on computer verification too large for any human to check by hand — raising the still-debated question of whether a proof we cannot fully survey gives genuine mathematical understanding. The rise of formal proof assistants (Lean, Coq) is reshaping this: in 2021 a community formally verified a deep result in condensed mathematics, hinting at a future where machine-checked proofs are the gold standard. Whether automated theorem provers will one day discover deep theorems, not merely verify them, remains open.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also