Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn7357Paper 3 · Pure and StatisticsPure content (sections A–J)Deduction, exhaustion and counterexample

Pure content (sections A–J) · Subtopic 65 of 66

Deduction, Exhaustion and Counterexample

A proof must work for every case, not just the ones you tried. Deduction uses algebra for a general case; exhaustion splits all possibilities into a few cases and checks each; and one single counterexample is enough to show a statement is false.

Edexcel YMA01 WMA12Edexcel 9MA0 Paper 1AQA 7357 Paper 1AQA 7357 Paper 2AQA 7357 Paper 3≈ 30 minRevision 5 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Write even, odd and consecutive integers algebraically.
Prove a statement by deduction.
Prove a statement by splitting into all possible cases.
Disprove a statement with a counterexample.

Pause and think

$n^2-n+41$ is prime for $n=1,2,3,\ldots,40$ . Is it prime for every positive integer $n$ ?

Section 2 of 14

Core idea

Start hereChecking isn't proving

$1+3=4$ , $5+7=12$ , $9+11=20$ : two odd numbers always seem to make an even number. But a thousand examples don't prove it for the next one. A proof covers every case at once by reasoning about a general number.

The big idea

Deduction: start from known facts and reason step by step. Exhaustion: check every possible case. Counterexample: one failure disproves a claim.

1. Proof by deduction

Why odd + odd is always even

Any odd number is pairs plus one left over. Two odd numbers have two leftovers, which make one more pair.

Even: $2n$ . Odd: $2n+1$ . Consecutive: $n$ , $n+1$ . ( $n$ an integer.)

Worked exampleOdd + odd is even

Prove the sum of two odd numbers is even.

Goal: General proof.
Strategy: Represent with algebra.

$2m+1,\ 2n+1$
Two odd numbers ( $m$ , $n$ integers; may differ).
$(2m+1)+(2n+1)=2(m+n+1)$
Add, factor 2.
$m+n+1\in\mathbb Z$
So the sum is $2\times$ integer: even ∎.

AnswerProved.

✓ Check

3+7=10=2(1+3+1)

with

m=1

n=3

✓.

Worked example $n^2-n$ is even

Prove for all integers $n$ .

Goal: Proof.
Strategy: Factorise.

$n^2-n=n(n-1)$
Factor.
$n,\ n-1\text{ consecutive}$
One of them is even, so the product is even ∎.

AnswerProved.

✓ Check

n=7

42

✓.

Worked example $x^2-6x+10>0$

Prove for all real $x$ .

Goal: Proof.
Strategy: Complete the square.

$x^2-6x+10=(x-3)^2+1$
$9+1=10$ .
$(x-3)^2\ge0\Rightarrow(x-3)^2+1\ge1>0$
Squares are non-negative ∎.

AnswerProved.

✓ CheckDiscriminant

36-40<0

also shows no roots ✓.

2. Exhaustion and counterexample

Worked exampleTwo quick claims

(a) Every square number ends in 0, 1, 4, 5, 6 or 9. (b) $2^n-1$ is prime for all positive integers $n$ .

Goal: Prove or disprove.
Strategy: (a) last digits are finite: check all. (b) look for a failure.

$0^2,\ldots,9^2\to0,1,4,9,6,5,6,9,4,1$
A square's last digit depends only on the last digit.
$n=4:\ 2^4-1=15=3\times5$
Counterexample.

Answer(a) true by exhaustion; (b) false.

✓ Check

n=2,3

give 3, 7 (prime): the claim looked true at first ✓.

Common misconceptionSame letter for both numbers Writing both odd numbers as

2n+1

only proves it for equal numbers.

Pause and think

Disprove: " $n^2+n+41$ is always prime."

Summary

Algebraic representation.
Exhaustion for finite cases.
One counterexample disproves.

Proof by deduction: Logical steps from known facts.
Counterexample: A case where the claim fails.

HistoryEuclid's standard. Euclid's Elements (about

300

BC) built all of geometry from a few axioms, with every result proved from earlier ones. It was used as a textbook for over

2000

years and set the standard of what a mathematical proof should look like.

Fun factA computer-checked exhaustion. The four colour theorem (any map can be coloured with four colours so neighbours differ) was proved in 1976 by splitting the problem into almost

2000

cases and checking them by computer: a proof by exhaustion on a gigantic scale.

Section 3 of 14

Key formulae

Even and odd

\text{even}=2n,\qquad\text{odd}=2n+1

Cases modulo 3

n=3k,\ 3k+1,\text{ or }3k+2

TrickFinish with a sentence. Every proof should end with a sentence that repeats the claim: "so the sum of three consecutive integers is always a multiple of

3

". Many mark schemes give the final mark only for that conclusion.

Section 4 of 14

Worked examples

Example 1 · Deduction0 / 2 steps

Prove that the sum of two odd numbers is even.

Example 2 · Exhaustion0 / 2 steps

Prove that every square number leaves remainder

0

1

when divided by

3

Section 5 of 14

Explore the graph

Is n² − n + 1 always prime?

Loading the interactive graph…

Try this

The point shows $k^2-k+1$ for whole numbers $k$ .
Step $k$ from $2$ upwards and test each value for primes: $3, 7, 13, \ldots$
Which is the first $k$ that gives a non-prime? That single value disproves the claim.

A pattern that holds for a few cases can still fail.

In the real worldSecurity relies on proofs. Online banking encryption depends on theorems about prime numbers. Engineers trust them because they are proved, not merely tested, so no future case can break them.

Section 6 of 14

Common mistakes

IncorrectTesting a few numbers as "proof"

CorrectUse algebra for the general case

Examples never cover every integer.

Incorrect

2n+1

and

2n+1

for two odd numbers

Correct

2m+1

and

2n+1

The same letter forces the numbers to be equal.

IncorrectExhaustion missing a case

CorrectList every case

e.g.

3k+2

as well as

3k

and

3k+1

IncorrectCounterexample that fails the condition

CorrectIt must meet the "if" part

Otherwise it says nothing about the statement.

Expectation

Checked it for $n=1,2,3$ . Proven.

Reality

One counterexample at $n=41$ and the whole claim collapses

Section 7 of 14

Exam tip

Exam tipState what your algebra shows. After the algebra, explain it in words: "

2(m+n+1)

is a multiple of

2

, so it is even." Algebra without the explanation often loses the final mark.

Section 8 of 14

Guided practice

SA-PROOF-0031 markL2 StandardCalculatorDeduction & exhaustion

Which line correctly starts a proof that the sum of any three consecutive integers is divisible by

3

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-PROOF-0041 markL2 StandardCalculatorDeduction & exhaustion

To prove that the sum of two odd numbers is even, the two odd numbers should be written as

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF1-0012 marksL2 StandardNon-calculatorDeduction & exhaustion

For every integer

n

(n+1)^2-(n-1)^2=kn

. Find

k

, which proves the difference is always a multiple of

k

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF-0051 markL2 StandardCalculatorDeduction & exhaustion

To prove by exhaustion that every square number leaves remainder

0

1

when divided by

3

, how many cases for

n

do you need?

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF-0061 markL3 ExamCalculatorDeduction & exhaustion

In the proof above, the case

n=3k+2

gives

n^2=9k^2+12k+4=3(3k^2+4k+1)+r

. Find

r

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF1-0031 markL1 FoundationNon-calculatorDeduction & exhaustion

To prove by exhaustion that no square number ends in the digit

7

, you check the last digit of

n^2

for each possible last digit of

n

. How many cases are there?

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF-0012 marksL1 FoundationCalculatorCounterexample

Find the smallest positive integer

n

for which

2^n+1

is not prime.

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF-0021 markL1 FoundationCalculatorCounterexample

Which value of

x

is a counterexample to "if

x^2>4

then

x>2

Salam Academy Original Practice · Proposed mark scheme

SA-PROOF1-0021 markL1 FoundationCalculatorCounterexample

Which pair is a counterexample to "the sum of two prime numbers is always even"?

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-PROOF-G012 marksL1 FoundationCalculatorCounterexample

The statement "

n^2-n+1

is prime for every integer

n\ge2

" is false. Find the smallest integer

n\ge2

that is a counterexample.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Even $2n$ , odd $2n+1$ ; different letters for independent numbers.
Deduction: general algebra to the exact conclusion.
Exhaustion: cover every case.
One counterexample disproves a statement.

Section 12 of 14

Quick quiz

Q1 · SA-PROOF-Q011 markL1 FoundationCalculatorCounterexample

How many counterexamples do you need to disprove a statement?

Salam Academy Original Practice · Proposed mark scheme

Q2 · SA-PROOF-Q021 markL1 FoundationCalculatorDeduction & exhaustion

Checking that a statement is true for

n=1

n=100

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: 7357 A-level Mathematics
Where: Section A, Proof
Expected: The same methods, examined on Paper 1 and Paper 2.
Calculator: Permitted; some answers must still be exact.
Typical style: AQA mixes short multiple-choice questions with longer structured ones.
Open in: 7357 · Paper 1 7357 · Paper 2 7357 · Paper 3

Section 14 of 14

Past paper questions

3 questions (15 marks) from real exams test this subtopic. Try each one under timed conditions, then mark it with the official mark scheme.

WMA12/01 · June 2025Question 104 marks
Proof by exhaustion about divisibility.
Question paper, page 30 Mark scheme
WMA12/01 · January 2025Question 85 marks
Counterexample about irrational numbers, and a proof about even numbers and multiples of 4.
Question paper, page 24 Mark scheme
WMA12/01 · June 2024Question 56 marks
Prove an inequality and give a counterexample.
Question paper, page 12 Mark scheme

All YMA01 past paper questions by topic

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: AQA 7357, First teaching 2017 (official specification).