Deductive Proof & Proof by Exhaustion

01Deductive Proof & Proof by Exhaustion

Proof Language

This section covers proof structure, logical symbols and the main sets of numbers.

Reasoning and notation

Proof is a mathematical argument that moves from given assumptions, through justified logical steps, to a conclusion. The conclusion must hold for the whole set of values stated in the question, such as all integers or all even integers.

LHS means left-hand side; RHS means right-hand side. Use logical symbols to show how one statement follows from another.

Notation	Meaning
$P\Rightarrow Q$	$P$ implies $Q$ : whenever $P$ is true, $Q$ must be true.
$P\Leftrightarrow Q$	$P$ is equivalent to $Q$ : $P$ is true if and only if $Q$ is true.

An implication gives a direction of reasoning. Use $\Leftrightarrow$ only when the reasoning works in both directions.

Number sets

Set	Numbers included
$\mathbb{N}$	The set of natural numbers.
$\mathbb{Z}$	The set of integers.
$\mathbb{Q}$	The set of rational numbers.
$\mathbb{R}$	The set of real numbers.

The sets nest inside one another: natural numbers are integers, integers are rational, and rational numbers are real.

The symbol $\mathbb{Z}$ denotes the integers.

02Deductive Proof & Proof by Exhaustion

Representing Integers

This section covers general forms for even and odd integers, multiples and consecutive integers.

Choose a form that captures every case

Represent numbers algebraically rather than choosing particular numerical examples. State when the letters used are integers.

Type of number	General form	What to state
Even integer	$2n$	$n$ is an integer.
Odd integer	$2n-1$	$n$ is an integer.
Multiple of an integer $m$	$km$	$k$ is an integer.
Three consecutive integers	$n-1,\ n,\ n+1$	$n$ is an integer; the terms differ by $1$ .
Three consecutive odd integers	$2n-3,\ 2n-1,\ 2n+1$	$n$ is an integer; the terms differ by $2$ .

Start with the middle term when representing three consecutive numbers, for example $n-1,n,n+1$ .

Worked example: a sum of consecutive odd integers

Show that adding any three consecutive odd integers gives a multiple of $3$ .

Let the integers be $2n-3$ , $2n-1$ and $2n+1$ , where $n$ is an integer. Their sum is

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

As $2n-1$ is an integer, the sum has the form $3k$ for an integer $k$ . It is therefore divisible by $3$ for every allowed $n$ .

03Deductive Proof & Proof by Exhaustion

Deduction

This section covers constructing a general algebraic proof and explaining its conclusion.

Build a general argument

Proof by deduction establishes a result by applying valid mathematical and logical steps to the starting assumptions. Algebra lets one argument cover every value in the stated number set.

1Define

Begin with a “Let…” statement. Introduce general numbers and state any integer or other restrictions.

2Transform

Use algebra to simplify or factorise, showing the logical steps towards the required form.

3Conclude

Explain why the final expression proves the claim, rather than leaving the reader to infer it.

For a divisibility claim, aim for an integer multiple of the required number. For an evenness claim, show that the result is twice an integer.

Testing a few values can help you notice a pattern. Try positive values, negative values and zero when they are allowed, but do not treat these checks as a general proof.

Worked example: squaring an even integer

Show that the square of an even integer is even.

Let $a=2n$ , where $n$ is an integer, so that $a$ represents any even integer. Then

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

Since $2n^2$ is an integer, $a^2$ is twice an integer and is therefore even. The argument applies to every even integer $a$ .

04Deductive Proof & Proof by Exhaustion

Identities

This section covers the distinction between equality and an identity.

Equality for every allowed value

Identity means an equality that holds for every allowed value of the variables. The symbol $\equiv$ emphasises that the two expressions are identical throughout the stated domain.

Equality: $P=Q$

The two sides have the same value. An equation involving variables may be true only for particular values; the symbol $=$ alone does not claim it holds for all values.

Identity: $P\equiv Q$

The expressions agree for every allowed value. No special choice of the variables is needed to make the equality true.

To justify an identity, the reasoning must apply across the whole domain. A few successful substitutions cannot establish this.

Keep $\equiv$ distinct from $\Leftrightarrow$ : the former compares expressions, while the latter states that two logical statements imply one another.

05Deductive Proof & Proof by Exhaustion

Inequality Proofs

This section covers non-negative squares and multiplying or dividing inequalities by positive numbers.

Squares and positive quantities

A square cannot be negative. For real $x$ , $x^2\ge 0$ .

Multiplying or dividing both sides of an inequality by a positive number preserves the direction of the inequality.

When this rule is used in a proof, the multiplier or divisor must be known to be positive.

06Deductive Proof & Proof by Exhaustion

Exhaustion

This section covers checking every permitted value and recognising the limits of direct testing.

Check the complete set of possibilities

Proof by exhaustion verifies a statement by checking every possibility allowed in the question. It is a proof only when the checks leave no permitted case untested.

Identify the complete set of values to be checked.
Evaluate each case and show that it has the required property.
Conclude that the result holds because every permitted case has been covered.

Worked example: one away from a multiple of seven

Show that $n^3+7$ is one away from a multiple of $7$ for each integer $n$ satisfying $1\le n\le4$ .

The only allowed values are $1$ , $2$ , $3$ and $4$ .

$n$	$n^3+7$	Multiple of $7$	Comparison
$1$	$1^3+7=8$	$7$	$8=7+1$
$2$	$2^3+7=15$	$14$	$15=14+1$
$3$	$3^3+7=34$	$35$	$34=35-1$
$4$	$4^3+7=71$	$70$	$71=70+1$

Every value is either $1$ above or $1$ below a multiple of $7$ . These are all the permitted integers, so the statement is proved by exhaustion.

When is direct testing practical?

You cannot check every member of an unlimited list one at a time. For example, listing multiples of $4$ can never finish a proof that all of them are even.

Keep a finite check as small as the reasoning allows. To show that a number is prime, it is enough to test possible factors up to its square root.

Exam Tip: If you are stuck, try the same method on a simpler case first. For example, before proving that $97$ is prime, think through the factor checks for a smaller prime such as $7$ or $11$ , then apply the same idea to $97$ .

07Deductive Proof & Proof by Exhaustion

Counterexamples

This section covers disproving universal statements with one valid counterexample.

One failure disproves an “always” claim

Counterexample is an allowed value, or collection of values, for which the claimed result is false. One valid counterexample disproves a statement that is meant to hold for every allowed case.

Check the restrictions before choosing values. A claim about integers must be tested with integers, not arbitrary real numbers; “distinct” requires the chosen numbers to be different.

Choose values that expose exceptions

What to try	Why it may help
$0$ and $1$ , when allowed	They can behave differently from other values. For example, $1+1\gt1\times1$ .
$2$	It is the only even prime. Also, $2+2=2^2$ , so addition and squaring can give the same result.
Irrational numbers	For a claim about real numbers, consider values such as $\pi$ , $e$ or $\sqrt{2}$ rather than testing only integers.
Trigonometric values	Different angles can have the same sine, which can defeat a claim that assumes they must be equal.

Worked example: a claim about three primes

Disprove the claim that adding any three distinct prime numbers always gives an odd total.

Choose the distinct primes $2$ , $5$ and $11$ . Their sum is

$2+5+11=18.$

The chosen numbers meet every condition, but $18$ is even. This single example makes the “always odd” claim false.