Mathematical proof

A mathematical proof is a logically complete argument showing that a statement must be true in every case allowed by its conditions. A calculation can verify one case and many examples can suggest a pattern, but neither proves a general claim.

At A-level you must be able to:

• prove statements by deduction
• prove statements by exhaustion
• prove statements by contradiction
• disprove a universal statement using a counterexample

The central skill is not memorising four templates. It is recognising what the statement claims, translating its definitions precisely, and choosing an argument that covers exactly the required cases.

Prerequisites

You should be able to:

• expand, factorise and rearrange algebraic expressions
• use the meanings of integer, factor, multiple, prime, even, odd, rational and irrational
• distinguish an identity from an equation
• read implications and inequalities accurately
• explain why each line of algebra follows from the previous line

Review proof and reasoning if words such as for every, there exists, implies or if and only if are unfamiliar. Review algebraic fluency if expanding and factorising interrupt your reasoning.

Statements, assumptions and conclusions

Many proof questions have the form

$$P\Rightarrow Q,$$

read as ”$P$ implies $Q$” or “if $P$, then $Q$”. Here $P$ is the hypothesis and $Q$ is the conclusion.

For example:

If an integer $n$ is divisible by $6$, then $n^2$ is divisible by $12$.

The hypothesis permits us to write $n=6k$ for some $k\in\mathbb Z$. The conclusion is what must be established:

$$n^2=(6k)^2=36k^2=12(3k^2).$$

Since $3k^2$ is an integer, $n^2$ is divisible by $12$.

That final sentence is essential. The algebra alone shows a form; the definition of divisibility turns the form into the conclusion.

Necessary does not mean sufficient

From $P\Rightarrow Q$, you cannot generally conclude $Q\Rightarrow P$.

$$n\text{ divisible by }6\Rightarrow n\text{ even}$$

is true, but its converse is false: $8$ is even and is not divisible by $6$.

An equivalence requires proof in both directions:

$$P\Leftrightarrow Q$$

means both $P\Rightarrow Q$ and $Q\Rightarrow P$.

The four proof methods

Method	Core idea	Best suited to
Deduction	Start from known facts and derive the conclusion	algebraic, divisibility and parity claims
Exhaustion	Split a finite set of possibilities into cases	parity, remainders and small finite domains
Contradiction	Assume the claim is false and derive an impossibility	irrationality and non-existence claims
Counterexample	Find one allowed case where a universal claim fails	disproving statements

The first three establish truth. A counterexample establishes falsity.

Proof by deduction

Deduction is a direct chain of valid implications. Begin with an arbitrary object satisfying the hypothesis, express the definitions algebraically, and work towards the required conclusion.

Worked example 1: consecutive squares

Prove that the difference between the squares of two consecutive integers is odd.

Let the consecutive integers be $n$ and $n+1$, where $n\in\mathbb Z$. Then

$$\begin{aligned} (n+1)^2-n^2 &=n^2+2n+1-n^2\\ &=2n+1. \end{aligned}$$

Since $n$ is an integer, $2n+1$ has the form $2k+1$ for an integer $k$, namely $k=n$. Therefore the difference is odd.

The letter $n$ represents an arbitrary integer, so the proof covers every pair of consecutive integers. Testing $4^2-3^2=7$ would cover only one pair.

Worked example 2: a polynomial factor

Prove that $n^3-n$ is divisible by $6$ for every integer $n$.

Factorise:

$$n^3-n=n(n^2-1)=n(n-1)(n+1).$$

These are three consecutive integers. Among any three consecutive integers:

• one is divisible by $3$
• at least one is even, so one is divisible by $2$

Therefore their product is divisible by $2\times3=6$. Hence $n^3-n$ is divisible by $6$.

This proof combines algebra with established facts about consecutive integers. Saying “the expression contains a factor $6$” would be inaccurate because the displayed factorisation does not literally show one factor equal to $6$.

Study the full method in proof by deduction and exhaustion.

Proof by exhaustion

Exhaustion proves a claim by checking every possible case. It is rigorous only when the cases are mutually exclusive and collectively cover the entire domain.

Worked example 3: square remainders

Prove that the square of any integer leaves remainder $0$ or $1$ when divided by $4$.

Every integer is either even or odd, so these two cases exhaust all possibilities.

Case 1: $n$ is even. Write $n=2k$ for some integer $k$. Then

$$n^2=4k^2,$$

so $n^2$ leaves remainder $0$ when divided by $4$.

Case 2: $n$ is odd. Write $n=2k+1$. Then

$$\begin{aligned} n^2&=(2k+1)^2\\ &=4k^2+4k+1\\ &=4(k^2+k)+1, \end{aligned}$$

so $n^2$ leaves remainder $1$ when divided by $4$.

Every integer is in exactly one of these cases. Therefore an integer square leaves remainder $0$ or $1$ modulo $4$.

Checking $n=0,1,2,3$ without explanation is incomplete unless you first justify why these represent all possible remainders modulo $4$. Exhaustion is about complete categories, not merely a long list.

Proof by contradiction

In a proof by contradiction, assume the exact negation of the desired result. If valid deductions lead to an impossibility, the assumption is false and the original statement is true.

The structure is

$$\neg P\Rightarrow\text{contradiction}\Rightarrow P.$$

Worked example 4: no smallest positive rational number

Prove that there is no smallest positive rational number.

Assume, for contradiction, that there is a smallest positive rational number $r$. Since $r>0$,

$$0<\frac r2<r.$$

Also, if $r=a/b$ for integers $a,b$ with $b\ne0$, then

$$\frac r2=\frac{a}{2b},$$

so $r/2$ is rational. We have constructed a positive rational number smaller than the supposed smallest one. This is a contradiction. Therefore no smallest positive rational number exists.

The contradiction must be identified explicitly. A result is not contradictory merely because it is unexpected.

Continue with proof by contradiction, including proofs involving irrational numbers and infinitely many primes.

Disproof by counterexample

A statement of the form

$$\text{for every }x\in S,\quad P(x)$$

is disproved by one value $c\in S$ for which $P(c)$ is false. The value must satisfy every condition in the claim.

Worked example 5: disprove an implication

Disprove:

For every integer $n$, if $n^2$ is even, then $n$ is divisible by $4$.

Take $n=2$. Then $n^2=4$ is even, so the hypothesis holds, but $2$ is not divisible by $4$, so the conclusion fails. Therefore $n=2$ is a counterexample and the statement is false.

A failed hypothesis is not a counterexample. For instance, $n=3$ does not help because $3^2$ is not even. Learn how to choose valid test cases in disproof by counterexample.

Definitions are proof tools

Informal intuition is useful for finding a route, but definitions make it rigorous.

Property	Algebraic form
$n$ is even	$n=2k$ for some $k\in\mathbb Z$
$n$ is odd	$n=2k+1$ for some $k\in\mathbb Z$
$a$ divides $b$	$b=ak$ for some $k\in\mathbb Z$
$r$ is rational	$r=a/b$ for $a,b\in\mathbb Z$, $b\ne0$
$p$ is prime	$p>1$ and its only positive factors are $1$ and $p$

Worked example 6: closure of rational numbers

Prove that the sum of two rational numbers is rational.

Let

$$x=\frac ab,\qquad y=\frac cd,$$

where $a,b,c,d\in\mathbb Z$ and $b,d\ne0$. Then

$$x+y=\frac ab+\frac cd=\frac{ad+bc}{bd}.$$

The numerator $ad+bc$ and denominator $bd$ are integers, and $bd\ne0$. Thus $x+y$ is a ratio of two integers with a non-zero denominator, so it is rational.

It is not enough to write “rational plus rational is rational” because that merely repeats the claim. The fraction form proves it from the definition.

Common misconceptions

Examples provide evidence, not universal proof

The first thousand values might fit a pattern while the next one fails. A proof must handle an arbitrary permitted value or a complete set of cases.

Algebra must preserve logic

Squaring can introduce extra possibilities. From $x=3$ we may deduce $x^2=9$, but from $x^2=9$ we obtain $x=3$ or $x=-3$. Use $\Rightarrow$ rather than $\Leftrightarrow$ when a step is not reversible.

A diagram is not usually a proof

A sketch can suggest relationships, but it may hide exceptional or badly scaled cases. Convert visual insight into algebra or a justified geometric theorem.

Do not prove the converse by accident

To prove “if $P$, then $Q$”, start with $P$ and reach $Q$. Starting with $Q$ and reaching $P$ proves the converse, which may be false.

Do not assume the conclusion

Using the statement you are trying to establish is circular reasoning. In contradiction, you assume its negation, not the statement itself.

Self-check

1. Identify the method

Which method is most natural for each task?

1. Prove that the product of two odd integers is odd.
2. Prove that $\sqrt{3}$ is irrational.
3. Prove a property separately for integers of the forms $3k$, $3k+1$ and $3k+2$.
4. Disprove “all prime numbers are odd”.

Answers

1. Deduction: write the integers as $2a+1$ and $2b+1$.
2. Contradiction: assume $\sqrt3=a/b$ in lowest terms.
3. Exhaustion: the three forms cover every integer remainder modulo $3$.
4. Counterexample: $2$ is prime but is not odd.

2. Complete a deduction

Prove that the sum of three consecutive integers is divisible by $3$.

Answer

Let the integers be $n-1$, $n$ and $n+1$, where $n\in\mathbb Z$. Their sum is

$$(n-1)+n+(n+1)=3n.$$

Since $n$ is an integer, $3n$ is divisible by $3$.

3. Find the logical gap

A student writes:

$5^2+1=26$, $7^2+1=50$ and $9^2+1=82$, all of which are even. Therefore $n^2+1$ is even for every odd integer $n$.

Why is this not a proof, and how can it be repaired?

Answer

Three examples do not cover every odd integer. Let $n=2k+1$, where $k\in\mathbb Z$. Then

$$\begin{aligned} n^2+1&=(2k+1)^2+1\\ &=4k^2+4k+2\\ &=2(2k^2+2k+1). \end{aligned}$$

The bracket is an integer, so $n^2+1$ is even.

4. Test a universal claim

Is the statement “for every real $x$, $x^2\geq x$” true? Prove or disprove it.

Answer

It is false. Take $x=\tfrac12$. Then

$$x^2=\frac14<\frac12=x.$$

Thus $x=\tfrac12$ is a counterexample.

Recommended learning route

1. Begin with proof by deduction and exhaustion to turn definitions into direct arguments and construct complete case splits.
2. Study proof by contradiction to learn precise negation and how an impossible consequence establishes a result.
3. Finish with disproof by counterexample to distinguish testing from proof and to attack false universal claims efficiently.
4. Apply the methods in communicating mathematical reasoning, where notation, justification and exam command words are treated explicitly.

When choosing a method, first ask what would settle the statement: a direct chain, a complete finite split, an impossible negation, or one failing case. That decision usually matters more than the algebra that follows.