Methods of Proof

A proof is the single thing that separates mathematics from every other field of human knowledge. In science you gather evidence and grow more confident; in mathematics you settle a question forever. Once a theorem is proved, no future experiment, computer, or clever counterexample can ever overturn it, because a proof is a chain of pure logical necessity leading from things we already accept to something new. Learning to prove is learning to know with certainty, and to make someone else know too.

This page teaches the four workhorse techniques you will use for the rest of your mathematical life — direct proof, proof by contrapositive, proof by contradiction, and mathematical induction — along with the deeper question underneath them all: what actually makes an argument valid?

Learning Objectives

• Explain what a proof is and what it means for an argument to be logically valid.
• Write a direct proof of an implication by starting from the hypothesis and reasoning to the conclusion.
• Use the contrapositive to prove statements that resist a direct attack.
• Construct a proof by contradiction, and recognize when it is the natural tool.
• Prove statements about all natural numbers using mathematical induction (and its strong form).
• Diagnose common logical errors: affirming the consequent, circular reasoning, and induction gaps.

Quick Answer

A direct proof of "if $P$ then $Q$" assumes $P$ and reasons forward step by step until it reaches $Q$. A proof by contrapositive instead proves the logically equivalent statement "if not $Q$ then not $P$." A proof by contradiction assumes the statement is false, then derives an impossibility, forcing the statement to be true. Mathematical induction proves a statement holds for every natural number by establishing a base case and showing each case implies the next, like an infinite line of falling dominoes. An argument is valid when the truth of its premises guarantees the truth of its conclusion — the conclusion cannot possibly be false while the premises are true.

Where It Came From

For most of human history, "proof" meant persuasion: a convincing speech or an authority's word. The revolution came with Euclid of Alexandria (around 300 BCE), whose Elements did something no one had done before — it started from a tiny handful of explicitly stated axioms and postulates and then derived hundreds of geometric theorems from them by pure deduction, each result justified only by earlier results. The need Euclid answered was intellectual: the Greeks had discovered that intuition lies. The Pythagoreans believed all lengths were ratios of whole numbers until someone proved $\sqrt{2}$ is irrational — a result you cannot see or measure, only prove. Once mathematics contained truths that contradicted intuition, only rigorous deduction could tell truth from plausible-looking falsehood.

Induction as a named, rigorous method is much younger. Informal versions appear in the work of the Islamic mathematician al-Karaji (around 1000 CE) and later Levi ben Gerson, but Blaise Pascal used it cleanly in the 1650s to prove properties of his arithmetic triangle, and Augustus De Morgan gave it the name "mathematical induction" in 1838.

The final chapter is formal proof theory. Through the 19th century, mathematicians like Frege, Peano, and Boole tried to reduce reasoning itself to symbolic rules, hoping to put all of mathematics on an unshakeable logical foundation. This program peaked with Hilbert and then hit a wall: in 1931 Kurt Gödel proved that any consistent formal system rich enough for arithmetic must contain true statements it cannot prove. Proof is powerful, but Gödel showed it has limits — a profound discovery born from taking proof itself as the object of study.

What Makes an Argument Valid

Before techniques, the foundation. A mathematical statement is built from premises (things assumed or already known) leading to a conclusion. The argument is valid if it is impossible for the premises to be true and the conclusion false at the same time. Validity is about form, not content.

The cornerstone rule is modus ponens: from "$P$" and "if $P$ then $Q$," conclude "$Q$." This is airtight. Contrast it with a seductive error, affirming the consequent: from "if $P$ then $Q$" and "$Q$," you may not conclude "$P$."

Worked example of the difference. Take "If it rained, the street is wet."

• Valid: It rained ($P$). Therefore the street is wet ($Q$). ✓
• Invalid: The street is wet ($Q$). Therefore it rained ($P$). ✗ — a burst pipe could explain the wet street.

Two logical equivalences power everything below. For any statement $P \Rightarrow Q$:

• Its contrapositive $\lnot Q \Rightarrow \lnot P$ is always equivalent to it.
• Its converse $Q \Rightarrow P$ is not equivalent (confusing the two is the affirming-the-consequent error).

Direct Proof: Reasoning Forward

The most natural method. To prove $P \Rightarrow Q$, you assume $P$ is true and build a chain of valid steps until you arrive at $Q$. Every step must be justified by a definition, an axiom, or a previously proven fact.

Theorem. If $n$ is an odd integer, then $n^2$ is odd.

Proof. Assume $n$ is odd. By definition, an odd integer can be written as $n = 2k + 1$ for some integer $k$. Then

$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$

Let $m = 2k^2 + 2k$, which is an integer because $k$ is. So $n^2 = 2m + 1$, which is by definition odd. Therefore $n^2$ is odd. $\blacksquare$

Notice the pattern: unpack the hypothesis using a definition, do honest algebra, then repackage the result to match the definition in the conclusion. The key move is naming things generally — we used a variable $k$, not a specific number, so the proof covers every odd integer at once.

Contrapositive: Turning the Statement Around

Sometimes assuming $P$ gives you nothing to grip. Because $P \Rightarrow Q$ is equivalent to $\lnot Q \Rightarrow \lnot P$, you can instead assume the conclusion is false and prove the hypothesis is false. This is a fully rigorous direct proof — just of the contrapositive.

Theorem. For an integer $n$, if $n^2$ is even, then $n$ is even.

A direct attack is awkward: from "$n^2$ is even" you would need to take a square root and argue about it. The contrapositive is clean.

Contrapositive. If $n$ is odd, then $n^2$ is odd.

Proof. We already proved exactly this above. Since the contrapositive is true, the original statement is true. $\blacksquare$

Rule of thumb: reach for the contrapositive when the negation of the conclusion is more concrete or easier to compute with than the hypothesis itself. Here, "$n$ is odd" gives us a formula to work with, while "$n^2$ is even" does not.

Proof by Contradiction: Assuming the Impossible

To prove a statement $S$, assume $\lnot S$ (that $S$ is false) and derive a contradiction — something that cannot possibly hold, like $0 = 1$ or "$x$ is both even and odd." Since a true premise can never lead to a falsehood through valid steps, the assumption $\lnot S$ must have been wrong, so $S$ is true. This is the tool for impossibility and non-existence results.

Theorem. $\sqrt{2}$ is irrational — it cannot be written as a fraction of two integers.

Proof. Suppose, for contradiction, that $\sqrt{2}$ is rational. Then $\sqrt{2} = \tfrac{a}{b}$ where $a, b$ are integers with no common factor (the fraction is fully reduced) and $b \neq 0$. Squaring both sides:

$2 = \frac{a^2}{b^2}, \quad\text{so}\quad a^2 = 2b^2.$

Then $a^2$ is even, and by our earlier theorem, $a$ must be even. Write $a = 2c$. Substituting:

$(2c)^2 = 2b^2 \;\Rightarrow\; 4c^2 = 2b^2 \;\Rightarrow\; b^2 = 2c^2.$

So $b^2$ is even, meaning $b$ is even too. But now $a$ and $b$ are both even — they share the factor $2$ — contradicting our assumption that the fraction was fully reduced. The assumption that $\sqrt{2}$ is rational is impossible. Therefore $\sqrt{2}$ is irrational. $\blacksquare$

This 2,000-year-old argument is one of the most beautiful in mathematics. Note how contradiction let us prove a negative ("no such fraction exists") that would be hopeless to attack directly — we can't check infinitely many fractions.

Mathematical Induction: The Domino Principle

Induction proves a statement $P(n)$ is true for all natural numbers $n \geq n_0$. It has two steps:

1. Base case: Prove $P(n_0)$ is true (usually $n_0 = 1$ or $0$).
2. Inductive step: Assume $P(k)$ is true for an arbitrary $k$ (the inductive hypothesis) and prove $P(k+1)$ follows.

If both hold, $P(n)$ is true for every $n \geq n_0$. Picture dominoes: the base case tips the first one, the inductive step guarantees each domino knocks over the next, so all of them fall.

Theorem. For every positive integer $n$,

$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.$

Proof.

Base case ($n = 1$): the left side is $1$; the right side is $\tfrac{1 \cdot 2}{2} = 1$. They match. ✓

Inductive step: Assume the formula holds for $n = k$, i.e.

$1 + 2 + \cdots + k = \frac{k(k+1)}{2}.$

We must show it holds for $n = k+1$. Add $k+1$ to both sides:

$1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1).$

Factor the right side over a common denominator:

$\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$

This is exactly the formula with $n = k+1$, since $(k+1)\big((k+1)+1\big)/2 = (k+1)(k+2)/2$. The inductive step holds. By induction, the formula is true for all positive integers $n$. $\blacksquare$

Strong induction is a variant where the inductive step may assume $P(1), P(2), \ldots, P(k)$ are all true (not just $P(k)$) to prove $P(k+1)$. It is logically equivalent to ordinary induction but far more convenient for results like "every integer greater than $1$ has a prime factorization," where breaking $k+1$ into factors sends you to smaller cases, not just the previous one.

Real-World Applications

• Program correctness: Software verification uses induction to prove loops and recursive functions are correct for all inputs — critical for aerospace, medical devices, and cryptographic code where a single bug is catastrophic.
• Cryptography: The RSA encryption protecting online banking rests on number-theory theorems (about primes and modular arithmetic) proved by contradiction and direct proof. Security is a mathematical guarantee, not a hope.
• Algorithm analysis: Proving an algorithm terminates and runs in a claimed time bound almost always uses induction on input size — the foundation of computer science.
• Formal verification and AI safety: Proof assistants like Coq and Lean mechanically check proofs step by step, used to certify compilers and even to formalize published theorems, directly descending from Hilbert's formal-proof program.

Common Mistakes

1. Affirming the consequent (assuming the converse). The misconception: Treating "if $P$ then $Q$" as if it also means "if $Q$ then $P$." Why it's wrong: An implication only runs one direction. "If a number is divisible by $4$, it is even" is true, but "if a number is even, it is divisible by $4$" is false ($6$ is a counterexample). The fix: To prove an "if and only if" ($P \Leftrightarrow Q$), you must prove both directions separately.

2. Proving with a specific example. The misconception: Checking that a claim works for $n = 1, 2, 3$ and declaring it proved. Why it's wrong: No finite number of examples establishes an infinite statement. The expression $n^2 + n + 41$ produces a prime for every $n$ from $0$ to $39$ — then fails at $n = 40$. Examples build intuition; they never prove. The fix: Use a general variable or induction to cover all cases at once. (Examples can disprove — one counterexample kills a universal claim.)

3. Forgetting the base case in induction. The misconception: Proving only the inductive step, thinking "$k \Rightarrow k+1$" is enough. Why it's wrong: Without a first domino, nothing falls. You can "prove" the false statement "$n = n+1$" by a valid inductive step ($n=k$ gives $k=k+1$, add $1$ to get $k+1 = k+2$) — but it has no valid base case, which is exactly why it fails. The fix: Always verify the base case explicitly, and check that your inductive step actually uses the hypothesis.

Comparison and Connections

All four methods aim at certainty but differ in strategy and in what they suit best.

Method	You assume...	You derive...	Best for
Direct proof	The hypothesis $P$	The conclusion $Q$	Straightforward implications
Contrapositive	$\lnot Q$	$\lnot P$	When $\lnot Q$ is more concrete than $P$
Contradiction	The statement is false	An impossibility	Non-existence, irrationality, "no such..."
Induction	$P(k)$ holds	$P(k+1)$ holds	Statements about all natural numbers

Contrapositive and contradiction are often confused. The contrapositive proves a specific equivalent implication and ends with $\lnot P$. Contradiction assumes the whole statement false and ends with any absurdity. In fact, a contrapositive proof can always be rephrased as a contradiction, but not vice versa. Induction connects deeply to recursion in computer science and to the well-ordering principle in number theory (every nonempty set of positive integers has a least element) — the two are logically equivalent.

Practice Questions

Recall

State the contrapositive and the converse of: "If $n$ is divisible by $6$, then $n$ is divisible by $3$." Answer: Contrapositive: "If $n$ is not divisible by $3$, then $n$ is not divisible by $6$" (true). Converse: "If $n$ is divisible by $3$, then $n$ is divisible by $6$" (false — $9$ is a counterexample).

Understanding

Explain why forgetting the base case makes an induction proof worthless, using the domino image. Guidance: The inductive step only guarantees each domino topples the next; without knocking over the first, the chain never starts and no domino need fall. The step establishes conditional truth ($P(k) \Rightarrow P(k+1)$); the base case supplies the unconditional starting truth.

Application

Prove by direct proof: the sum of two even integers is even. Answer: Let the integers be $2a$ and $2b$ for integers $a, b$. Their sum is $2a + 2b = 2(a+b)$. Since $a+b$ is an integer, the sum is even. $\blacksquare$

Analysis

Prove by induction that $n^2 \geq 2n + 1$ for all integers $n \geq 3$. Where does the base case matter? Guidance: Base case $n=3$: $9 \geq 7$. ✓ Assume $k^2 \geq 2k+1$. Then $(k+1)^2 = k^2 + 2k + 1 \geq (2k+1) + 2k + 1 = 4k + 2 \geq 2(k+1)+1 = 2k+3$ since $4k+2 \geq 2k+3 \Leftrightarrow 2k \geq 1$, true for $k \geq 3$. The base case matters because the claim actually fails for $n = 1$ ($1 \geq 3$ is false), so starting at $3$ is essential.

FAQ

Is a proof by contradiction less "valid" than a direct proof? No — it is completely rigorous and standard. Some mathematicians (constructivists) prefer direct/constructive proofs because they build the object rather than just show its non-existence is impossible, but for classical mathematics all four methods are equally valid.

How do I know which method to use? Try direct proof first — it's the most natural. If the hypothesis gives you nothing to work with, look at the contrapositive. For "there is no such thing" or irrationality claims, reach for contradiction. If the statement is "for all natural numbers $n$," think induction.

What's the difference between the converse and the contrapositive? The contrapositive ($\lnot Q \Rightarrow \lnot P$) is always equivalent to the original. The converse ($Q \Rightarrow P$) is a genuinely different statement that may be true or false independently. Swapping them is a classic logical trap.

Can I prove something is true just by testing lots of examples? No. Examples can disprove a universal statement (one counterexample suffices) but can never prove one, no matter how many you check. Infinitely many cases require a general argument.

Why is the inductive hypothesis allowed — isn't assuming $P(k)$ circular? It isn't circular because you never assume the thing you're proving for all $n$. You assume it for one arbitrary $k$ and show that forces $P(k+1)$. Combined with the base case, this creates a valid chain covering every $n$ — you're proving an implication, not the whole result outright.

What did Gödel prove about proofs? That any consistent formal system powerful enough to describe arithmetic contains true statements that cannot be proved within that system. It doesn't mean those statements are unknowable — it means no single fixed set of axioms captures all mathematical truth.

Quick Revision

• Valid argument: premises being true makes it impossible for the conclusion to be false.
• Modus ponens (valid): $P$, and $P \Rightarrow Q$, therefore $Q$. Affirming the consequent (invalid): $Q$, and $P \Rightarrow Q$, therefore $P$.
• $P \Rightarrow Q$ is equivalent to its contrapositive $\lnot Q \Rightarrow \lnot P$, not to its converse $Q \Rightarrow P$.
• Direct: assume $P$, derive $Q$. Contrapositive: assume $\lnot Q$, derive $\lnot P$. Contradiction: assume statement false, derive an absurdity.
• Induction: prove base case $P(n_0)$ and inductive step $P(k) \Rightarrow P(k+1)$. Never skip the base case.
• Key results to remember: $1+2+\cdots+n = \tfrac{n(n+1)}{2}$; $\sqrt{2}$ is irrational (by contradiction); one counterexample disproves, no number of examples proves.

Related Topics

Prerequisites

• Discrete Mathematics overview

Related Topics

• Logic and truth tables (foundations of valid inference)
• Set theory and quantifiers ("for all" and "there exists")

Next Topics

• Number theory: divisibility and prime factorization (built on these methods)
• Recursion and recurrence relations (the algorithmic cousin of induction)