Proof by deduction and exhaustion

A mathematical proof shows that a claim must be true in every case it covers. Two important A-level methods are:

• deduction, where established facts and definitions are linked in a logically valid chain;
• exhaustion, where every possible case in a finite set is checked.

The hard part is usually not the algebra. It is representing the claim generally enough, justifying each implication, and knowing when all cases have genuinely been covered.

Prerequisites

You should be able to:

• expand, factorise and rearrange algebraic expressions;
• use integer notation such as $n\in\mathbb Z$;
• recognise factors, multiples, odd numbers and even numbers;
• distinguish a universal claim, such as “for every integer”, from a claim about one example.

Review algebraic proof and mathematical reasoning or algebraic fluency if these ideas are uncertain.

What deduction means

A deductive proof starts from the hypothesis and moves through statements that follow necessarily from what is already known. Its basic shape is

$$P\implies P_1\implies P_2\implies\cdots\implies Q.$$

If $P$ is the given information and $Q$ is the required conclusion, the chain proves $P\implies Q$.

For example, if $n$ is even, then $n=2k$ for some $k\in\mathbb Z$. Therefore

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

Since $2k^2\in\mathbb Z$, $n^2$ has the form $2m$ for an integer $m$. Hence $n^2$ is even.

The last sentence matters. The algebra produces a form; the definition turns that form into the conclusion.

Arbitrary does not mean unknown

An arbitrary integer $n$ represents every integer satisfying the hypothesis. Proving the result for this general $n$ proves it for the whole class. Checking $n=2,4,6$ proves only three cases.

Translating definitions into algebra

Direct proofs become manageable when verbal properties are written in a usable form.

Property	Algebraic form
$n$ is even	$n=2k$, $k\in\mathbb Z$
$n$ is odd	$n=2k+1$, $k\in\mathbb Z$
$n$ is a multiple of $d$	$n=dk$, $k\in\mathbb Z$
$a$ divides $b$	$b=ak$, $k\in\mathbb Z$
$x$ is rational	$x=\frac pq$, $p,q\in\mathbb Z$, $q\ne0$
$x$ is positive	$x>0$

Use different integer parameters for quantities that may differ. Two arbitrary odd integers should normally be written $2a+1$ and $2b+1$, not both as $2k+1$.

Worked example 1: sum of two odd integers

Prove that the sum of any two odd integers is even.

Let the odd integers be $2a+1$ and $2b+1$, where $a,b\in\mathbb Z$. Their sum is

$$\begin{aligned} (2a+1)+(2b+1) &=2a+2b+2\\ &=2(a+b+1). \end{aligned}$$

Since $a+b+1\in\mathbb Z$, the sum is twice an integer. Therefore it is even.

This proof covers negative odd integers too. No positivity was assumed.

Worked example 2: an odd square

Prove that the square of an odd integer is odd.

Let $n=2k+1$, where $k\in\mathbb Z$. Then

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

The number $2k^2+2k$ is an integer, so $n^2$ has the form $2m+1$. Hence $n^2$ is odd.

Do not assume the conclusion

Writing “let $n^2=2k+1$” assumes that $n^2$ is odd, which is precisely what must be proved. Represent the hypothesis, $n$ is odd, and deduce the conclusion from it.

Self-check 1

Prove that the product of an even integer and any integer is even.

Answer

Let the even integer be $2k$ and let the other integer be $m$, where $k,m\in\mathbb Z$. Then

$$(2k)m=2(km).$$

Since $km\in\mathbb Z$, the product is twice an integer and is therefore even.

Divisibility proofs

To prove that an expression is divisible by $d$, rewrite it as $d$ multiplied by an integer. Merely obtaining a decimal or checking several substitutions is not enough.

Worked example 3: consecutive integers

Prove that the product of three consecutive integers is divisible by $6$.

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

Among any two consecutive integers, one is even. Therefore the product $n(n+1)(n+2)$ has a factor of $2$.

Every integer has one of the forms

$$3q,\qquad 3q+1,\qquad 3q+2.$$

If $n=3q$, then $n$ is divisible by $3$. If $n=3q+1$, then $n+2=3(q+1)$ is divisible by $3$. If $n=3q+2$, then $n+1=3(q+1)$ is divisible by $3$.

Thus the product has a factor of $2$ and a factor of $3$. Since $2$ and $3$ are coprime, it is divisible by $6$.

This is deduction containing a small exhaustive case split. Methods can work together.

Worked example 4: a factorisation that exposes divisibility

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. By the previous result, their product is divisible by $6$. Hence $n^3-n$ is divisible by $6$.

Notice the efficient structure: an established result may be used once its conditions are matched exactly.

Self-check 2

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

Answer

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

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

Since $n\in\mathbb Z$, this has the form $2k+1$ for an integer $k$. Therefore the difference is odd.

Deduction with inequalities

An inequality proof must preserve direction correctly. You may:

• add or subtract the same expression on both sides;
• multiply by a known positive quantity without reversing the sign;
• multiply by a known negative quantity only if the sign is reversed;
• use a square such as $(x-a)^2\geq0$ for real $x$.

Worked example 5: starting from a non-negative square

Prove that

$$x+\frac1x\geq2$$

for every $x>0$.

For real $x$,

$$(x-1)^2\geq0.$$

Expanding gives

$$x^2-2x+1\geq0,$$

so

$$x^2+1\geq2x.$$

Because $x>0$, division by $x$ preserves the inequality:

$$x+\frac1x\geq2.$$

Equality occurs when $(x-1)^2=0$, so equality holds precisely at $x=1$.

The domain carries logical information

If $x$ were negative, dividing by $x$ would reverse the inequality. If $x=0$, $1/x$ would be undefined. State and use the domain rather than treating it as decoration.

Worked example 6: proving one expression is larger

Prove that $x^2+4>4x-1$ for every real $x$.

Consider the difference:

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

For every real $x$, $(x-2)^2\geq0$, so $(x-2)^2+1>0$. Therefore

$$x^2+4>4x-1$$

for every real $x$.

Self-check 3

Prove that $a^2+b^2\geq2ab$ for all real $a$ and $b$. When does equality hold?

Answer

Since every real square is non-negative,

$$(a-b)^2\geq0.$$

Therefore

$$a^2-2ab+b^2\geq0,$$

which rearranges to

$$a^2+b^2\geq2ab.$$

Equality holds precisely when $(a-b)^2=0$, which means $a=b$.

Identities and equations are different

An identity is true for every value in its stated domain. An equation may be true only for particular values.

To prove an identity, start from one side and use valid algebra to reach the other, or show that both sides equal the same expression. Do not begin by writing the target equality and then manipulate it as though it were already known.

Worked example 7: a rational identity

Prove that, for $x\ne2,-2$,

$$\frac1{x-2}-\frac1{x+2}=\frac4{x^2-4}.$$

Starting from the left-hand side,

$$\begin{aligned} \frac1{x-2}-\frac1{x+2} &=\frac{x+2-(x-2)}{(x-2)(x+2)}\\ &=\frac4{x^2-4}, \end{aligned}$$

which is the right-hand side. The restrictions ensure that no denominator is zero.

Checking $x=3$ would confirm only one value. It would not prove the identity.

Proof by exhaustion

Proof by exhaustion divides the claim into a finite list of possible cases and proves each one. It is valid only when:

1. the cases cover every possibility;
2. no case is left as “similar” without adequate justification;
3. the conclusion is verified in each case.

The list may be written explicitly, or generated systematically using parity, remainders, signs or a finite range.

Worked example 8: explicit finite checking

Prove that $n^2+n+41$ is prime for every integer $n$ satisfying $0\leq n\leq5$.

There are exactly six possible integers:

$$\begin{array}{c|cccccc} n&0&1&2&3&4&5\\ \hline n^2+n+41&41&43&47&53&61&71 \end{array}$$

Each output is prime. Since the table covers every integer in the stated range, the claim is proved.

This does not prove the expression prime for all non-negative integers. Indeed, at $n=40$,

$$40^2+40+41=41^2,$$

which is composite.

Worked example 9: exhaustion by remainders

Prove that every integer square leaves remainder $0$ or $1$ when divided by $4$.

Every integer has exactly one of the forms

$$4q,quad4q+1,quad4q+2,quad4q+3,$$

where $q\in\mathbb Z$. Squaring each form gives

$$\begin{aligned} (4q)^2&=4(4q^2),\\ (4q+1)^2&=4(4q^2+2q)+1,\\ (4q+2)^2&=4(4q^2+4q+1),\\ (4q+3)^2&=4(4q^2+6q+2)+1. \end{aligned}$$

The first and third forms have remainder $0$ on division by $4$; the second and fourth have remainder $1$. These four cases exhaust all integers, so the result follows.

A shorter parity split also works. If $n=2k$, then $n^2=4k^2$. If $n=2k+1$, then $n^2=4(k^2+k)+1$.

Worked example 10: choosing cases economically

Prove that $n(n+1)$ is even for every integer $n$ by exhaustion.

Every integer is either even or odd.

• If $n=2k$, then $n(n+1)=2k(2k+1)=2[k(2k+1)]$, so the product is even.
• If $n=2k+1$, then $n+1=2k+2=2(k+1)$, so $n(n+1)=2[(2k+1)(k+1)]$, which is even.

The even and odd cases cover all integers. Therefore $n(n+1)$ is always even.

Self-check 4

Prove that $n^2+n+1$ is odd when $n$ is even and odd when $n$ is odd. Hence prove it is odd for every integer $n$.

Answer

If $n=2k$, then

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

which is odd.

If $n=2k+1$, then

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

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

Deduction or exhaustion?

Choose the method that makes completeness easiest to see.

Feature of the problem	Natural approach
A general algebraic implication	Deduction from definitions
A finite stated list or bounded integer range	Exhaustion
Behaviour depends on odd or even input	Exhaustion into two parity cases
Behaviour depends on remainder after division by $d$	Exhaustion into $d$ residue cases
A useful factorisation or non-negative square is visible	Deduction

Exhaustion is not less rigorous than symbolic deduction. It becomes weak only when the list is incomplete or when a large sample is mistaken for every case.

Common misconceptions

”Many examples make a proof”

Examples provide evidence and may reveal a pattern. A universal statement has infinitely many possible inputs, so no finite sample proves it. Use an arbitrary input or a genuinely exhaustive classification.

”The final algebraic line speaks for itself”

If you obtain $2(k^2+k)$, say that $k^2+k$ is an integer and therefore the expression is even. Connect the algebra to the required definition.

”Cases chosen at random are exhaustive”

The cases $n=1,2,3$ are exhaustive only if the domain is exactly $\{1,2,3\}$. By contrast, “even or odd” is exhaustive for integers because every integer has exactly one of those properties.

”Reversible algebra automatically gives a forward proof”

Working backwards can help discover a proof, but the presented argument must show that the hypothesis implies the conclusion. This is especially important if a step such as squaring could introduce extra possibilities.

”A diagram proves the claim”

A diagram can suggest a construction, but it may not be drawn accurately or represent every configuration. A geometric proof must cite established facts such as equal radii, parallel-line angle rules or congruence conditions.

Mixed self-check

1. Prove that the sum of three consecutive integers is divisible by $3$.
2. Prove that $(x+1)^2\geq4x$ for all real $x$.
3. An integer $n$ satisfies $1\leq n\leq4$. Prove by exhaustion that $n^2+n$ is even.
4. Explain why checking the first $1000$ positive integers cannot prove that $n^2+n+41$ is always prime.

Answers

1. Write the integers as $n-1,n,n+1$. Their sum is $3n$, which is divisible by $3$ because $n\in\mathbb Z$.

2. The difference between the two sides is

   $$(x+1)^2-4x=x^2-2x+1=(x-1)^2\geq0.$$

   Therefore $(x+1)^2\geq4x$. Equality holds at $x=1$.

3. The four values of $n^2+n$ are

   $$2,\quad6,\quad12,\quad20.$$

   Each is even, and $1,2,3,4$ are all possible integer values in the stated range.

4. The claim concerns infinitely many positive integers. Checking $1000$ of them leaves infinitely many unchecked. In fact $n=40$ gives $41^2$, so the claim is false even within that sample.

Proof checklist

Before finishing a proof, ask:

1. Have I stated the domain of each new variable?
2. Have I represented the hypothesis, rather than assumed the conclusion?
3. Does every line follow from the previous information?
4. If I split into cases, have I explained why they are exhaustive?
5. Have I connected the final algebraic form to the required conclusion?
6. Have I respected restrictions such as non-zero denominators and positive divisors?

Next steps

Direct deduction proves a claim by moving forward from its hypothesis. When assuming the opposite exposes an impossibility more naturally, use proof by contradiction. When a universal statement is false, a single valid example can disprove it, as explained in disproof by counterexample.

For clearer exam presentation, continue to communicating mathematical reasoning. Deductive arguments also recur in trigonometric proof and modelling and throughout algebra and calculus.