A1 - Deduction, exhaustion and counterexamples | AQA A-Level Mathematics

A proof explains why a claim follows from its assumptions for every case it covers. You will use general algebra, complete case splits and counterexamples to decide whether claims are true. Precise language will help you distinguish a proof from a convincing pattern.

Claims, domains and logical symbols

The expression $n^2+n+41$ is prime at every integer from $0$ to $39$ . Can forty consecutive successes prove that it is prime for every non-negative integer?

Recall that a prime is an integer greater than $1$ with no positive divisors except $1$ and itself. For example, $7$ is prime, whereas $25=5\times5$ is composite. The number $1$ is neither prime nor composite.

Start with a few of those successes:

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

The pattern is striking. But a claim about every allowed integer includes values beyond the ones checked. Keep the question in mind: by the end, you will know exactly what settles it.

You already know

Expanding brackets gives $(x+2)^2=x^2+4x+4$ . Solving $x^2=4$ gives two real solutions, $x=2$ and $x=-2$ . Algebraic steps must preserve every allowed solution.

The domain is the set of allowed values. In AQA's notation, $\mathbb N=\{1,2,3,\ldots\}$ contains the natural numbers, so it excludes zero. The integers $\mathbb Z$ include zero and negative whole numbers; $\mathbb Z^+$ contains the positive integers. The rational numbers $\mathbb Q$ are numbers expressible as integer fractions with nonzero denominator, and $\mathbb R$ contains all real numbers. For example, $-3\in\mathbb Z$ , $\frac12\in\mathbb Q$ and $\sqrt2\in\mathbb R$ . A claim about $\mathbb Z^+$ need not hold throughout $\mathbb R$ .

Proof

A proof is a logical argument that starts from given assumptions or established facts and reaches the claimed conclusion through justified steps. It must cover the full stated domain. Checking $n=1$ proves a statement about that value; it does not prove a statement about every positive integer.

Mathematical words describe different objects. In the expression $n^2+3n+2$ , the letter $n$ is a variable. Its three terms are $n^2$ , $3n$ and $2$ ; the coefficient of $n$ is $3$ ; the constant term is $2$ ; and the index in $n^2$ is $2$ . Writing $f(n)=n^2+3n+2$ defines a function, which assigns one output to each allowed input.

An equation, such as $x^2=4$ , asserts equality at its solutions. An identity, such as $(x+2)^2\equiv x^2+4x+4$ , asserts equality for every allowed value. The sign $=$ means “equals”, $\ne$ means “is not equal to”, and $\equiv$ marks an identity here. Thus $x^2\equiv4$ would be false for a real variable: at $x=0$ , its two sides differ.

Other relation symbols make the meaning of a statement precise.

The inequality signs $<$ and $>$ are strict: equality is excluded. The signs $\le$ and $\ge$ include equality. Use $\approx$ for an approximation, as in $\frac13\approx0.333$ , rather than claiming exact equality. The statement $y\propto x$ means $y=kx$ for a fixed nonzero constant $k$ ; for example, $y=3x$ gives direct proportion. The symbol $\infty$ means infinity, not a final largest number. You will use these symbols with functions later in the course.

The following symbols connect whole statements:

Symbol	Meaning
$p\Rightarrow q$	If $p$ is true, then $q$ is true.
$p\Leftarrow q$	$p$ is implied by $q$ ; the direction is $q\Rightarrow p$ .
$p\Leftrightarrow q$	$p$ is true if and only if $q$ is true; both directions hold.
$\therefore$	Therefore: introduces a conclusion.
$\because$	Because: introduces a reason.

For a real variable, $x=2\Rightarrow x^2=4$ is valid. Reversing it loses the solution $x=-2$ . The reversible statement is

x^2=4\Leftrightarrow(x=2\text{ or }x=-2)

Restricting the domain to $x>0$ would make $x^2=4\Leftrightarrow x=2$ valid. The domain is part of the claim, not a detail to add afterwards. This identity and these logical rules are not in the formula booklet: learn their meaning rather than a string of symbols.

Key idea

State what values are allowed and justify the direction of each implication. “If and only if” needs both directions.

The next check distinguishes an equation's complete solution set from one possible solution.

Deduction with general integers

A general representation lets one argument cover infinitely many integers.

For example, $3+7=10$ and $(-5)+9=4$ suggest that adding odd integers gives an even integer. Deduction means establishing that conclusion from assumptions and known facts, rather than relying on the examples.

Even and odd integers

For $k\in\mathbb Z$ ,

\text{even integer}=2k\qquad\text{odd integer}=2k+1

For a nonzero integer $d$ , an integer $a$ is divisible by $d$ exactly when $a=dm$ for some $m\in\mathbb Z$ .

Not in the formula booklet: learn it.

These forms include negative values: $-3=2(-2)+1$ . “Let an arbitrary odd integer be $2k+1$ ” means that $k$ is unspecified, so the proof cannot depend on one chosen value. For two arbitrary odd integers, use $2r+1$ and $2s+1$ . Reusing $k$ for both would assume that they are equal. Consecutive odd integers do have a stated relationship, so they can be written as $2k+1$ and $2k+3$ .

Worked example 1: adding arbitrary odd integers

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

Plan. Give the integers independent parameters, add them and factor out $2$ .

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

\begin{aligned} (2r+1)+(2s+1) &= 2r+2s+2 && \text{collect terms} \\ &= 2(r+s+1) && \text{factor out }2 \end{aligned}

Why this step? The factorised form shows twice an integer; an expanded expression alone does not yet state the parity reason.

Answer. Since $r+s+1$ is an integer, the sum is even for every pair of odd integers.

Check. For the unequal pair $-3$ and $7$ , use $r=-2$ , $s=3$ . The formula gives $2(-2+3+1)=4$ , agreeing with $-3+7=4$ . This checks the algebra, while the arbitrary parameters provide the proof.

Worked example 2 changes the operation from addition to multiplication. Keep the same independent representations; the target is now the odd form.

Worked example 2: multiplying arbitrary odd integers

Question. Prove that the product of any two odd integers is odd.

Plan. Expand the product and put it in the form twice an integer plus one.

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

\begin{aligned} (2r+1)(2s+1) &= 4rs+2r+2s+1 && \text{expand} \\ &= 2(2rs+r+s)+1 && \text{expose the odd form} \end{aligned}

Why this step? The expression $2rs+r+s$ is an integer, so the final $+1$ makes the product odd.

Answer. Every product of two odd integers is odd.

Check. With $r=-2$ , $s=3$ , the expression is $2(-12-2+3)+1=-21$ , agreeing with $(-3)\times7=-21$ .

Taking the two odd integers to be equal also proves that every odd integer has an odd square. For an even integer, $(2k)^2=2(2k^2)$ is even. These parity results, and the sum and product results just proved, are not in the formula booklet: derive them from the general forms when a proof is requested.

Watch out

Wrong: “Let the two odd integers both be $2k+1$ .” That proves only a claim about equal integers. Right: use independent integer parameters unless the question gives a relationship between the integers.

The next question changes the operation again, to subtraction. AQA's “Prove” requires the general working and a concluding statement; a list of successful examples is insufficient.

Proof by exhaustion

Exhaustion turns a collection of cases into a proof by showing that no possible case has been omitted.

The square $5^2=25$ leaves remainder $1$ on division by $3$ , as does $7^2=49$ . Rather than checking more integers, classify every integer by its remainder. Each belongs to exactly one of the forms $3k$ , $3k+1$ , $3k+2$ , with $k\in\mathbb Z$ . Negative integers are included: $-1=3(-1)+2$ .

Proof by exhaustion

A proof by exhaustion treats every possible case and establishes the conclusion in each one. The domain may be finite, or an infinite domain may split into finitely many general cases. Checking three specific integers is not the same as checking three cases that cover all integers.

For division by a positive integer $d$ , the possible remainders are $0,1,\ldots,d-1$ . Writing $n=dk+r$ , with integer $k$ , makes each remainder case general. This division property is not in the formula booklet: learn how it makes a case split complete.

Worked example 3: square remainders on division by three

Question. Prove that an integer square has remainder $0$ or $1$ when divided by $3$ .

Plan. Square each of the three possible general remainder forms and isolate a multiple of $3$ .

For $k\in\mathbb Z$ :

\begin{aligned} n=3k &\Rightarrow n^2=3(3k^2) && \text{remainder }0 \\ n=3k+1 &\Rightarrow n^2=3(3k^2+2k)+1 && \text{remainder }1 \\ n=3k+2 &\Rightarrow n^2=3(3k^2+4k+1)+1 && \text{remainder }1 \end{aligned}

Why this step? The forms cover every integer, and every bracket is an integer. The remainders therefore apply to all values in each case.

Answer. Every integer square has remainder $0$ or $1$ on division by $3$ ; remainder $2$ is impossible.

Check. The last expansion is $9k^2+12k+4$ , equal to $(3k+2)^2$ . At $n=-1$ , the square is $1$ , consistent with that case.

Worked example 4 changes the divisor from $3$ to $4$ . There are now four remainder cases, so reusing only the previous three would leave a gap.

Worked example 4: square remainders on division by four

Question. Prove that an integer square has remainder $0$ or $1$ when divided by $4$ .

Plan. Use all four possible remainders of the integer before squaring.

For $k\in\mathbb Z$ :

\begin{aligned} n=4k &\Rightarrow n^2=4(4k^2) && \text{remainder }0 \\ n=4k+1 &\Rightarrow n^2=4(4k^2+2k)+1 && \text{remainder }1 \\ n=4k+2 &\Rightarrow n^2=4(4k^2+4k+1) && \text{remainder }0 \\ n=4k+3 &\Rightarrow n^2=4(4k^2+6k+2)+1 && \text{remainder }1 \end{aligned}

Why this step? Squaring the general forms shows what happens to every integer with that remainder, not just to $0,1,2,3$ .

Answer. The four exhaustive cases give only remainder $0$ or $1$ , proving the claim.

Check. At $n=6=4(1)+2$ , $n^2=36=4(9)$ . At $n=7=4(1)+3$ , $n^2=49=4(12)+1$ .

A shorter proof of the second result uses the two exhaustive cases even and odd: $(2k)^2=4k^2$ , whereas $(2k+1)^2=4k(k+1)+1$ . Choose cases that make the working simple, then explain why they cover the domain. These square-remainder results are not in the formula booklet: establish them when needed.

Exhaustion can also check a genuinely finite list. For example, to prove that $103$ is prime, it is enough to test the primes $2,3,5,7$ . A composite integer $N>1$ has a prime divisor at most $\sqrt N$ : in a factor pair, at least one factor is at most $\sqrt N$ , and that factor has a prime divisor. Here $10<\sqrt{103}<11$ , and

103=2(51)+1=3(34)+1=5(20)+3=7(14)+5

None of the possible small prime divisors divides $103$ , so $103$ is prime. The bound explains why the list is complete. This prime-divisor bound is not in the formula booklet: understand its factor-pair justification.

Watch out

Wrong: “The claim holds for $n=0,1,2$ , so it holds for every integer.” Those are three values. Right: use $n=3k,3k+1,3k+2$ , with arbitrary integer $k$ , to cover three complete remainder classes.

The next question changes the expression in Worked example 4 by adding $2$ . Use the shorter even/odd split requested in the question.

Counterexamples and domain boundaries

One allowed input that makes a universal claim false is enough to disprove the claim.

“For every” and “for all” make universal claims. By contrast, “there exists” means at least one suitable example exists. One example can establish existence; proving a universal claim needs an argument covering every case.

Counterexample

A counterexample satisfies a claim's assumptions but violates its conclusion. For “every positive real number $x$ satisfies $x^2\ge x$ ”, the value $x=\frac12$ is a counterexample because $\frac14<\frac12$ . The value $x=-1$ is not: it is outside the stated domain and does not violate the inequality anyway.

Look near domain boundaries, at equality cases and at simple fractions. For the claim just discussed, $x=1$ gives equality, so it does not refute $x^2\ge x$ . The claim is true for positive integers, since $n\ge1$ gives $n^2\ge n$ , but extending it to positive reals introduces the interval $0<x<1$ . These inequalities are not in the formula booklet: justify them from their domains.

Worked example 5: disproving a prime-producing claim

Question. Use a counter example to show that “ $n^2+n+5$ is prime for every positive integer $n$ ” is incorrect.

Plan. Try an input one less than the constant term, then display a nontrivial factorisation.

Choose $n=4$ , a positive integer. Then

\begin{aligned} n^2+n+5 &= 4^2+4+5 && \text{substitute an allowed input} \\ &= 25 && \text{evaluate} \\ &= 5\times5 && \text{show nontrivial factors} \end{aligned}

Why this step? A composite output must be demonstrated, not merely asserted; the factors show exactly why this value is not prime.

Answer. The allowed value $n=4$ gives a composite number, so the universal claim is false.

Check. $5\times5=25$ , and each factor is greater than $1$ . The failure does not mean that the expression is never prime: at $n=1$ , it equals $7$ .

Worked example 6 changes only the constant from $5$ to $11$ . The same choice of an input one below the constant exposes a square.

Worked example 6: changing the constant

Question. Use a counter example to show that “ $n^2+n+11$ is prime for every positive integer $n$ ” is incorrect.

Plan. Use $n=10$ , check its domain and factor the resulting value.

\begin{aligned} 10^2+10+11 &= 100+10+11 && \text{substitute }n=10 \\ &= 121 && \text{evaluate} \\ &= 11\times11 && \text{a composite value} \end{aligned}

Why this step? With constant $c$ , the input $n=c-1$ gives $(c-1)^2+(c-1)+c=c^2$ . For an integer $c>1$ , this is a valid positive input and a non-prime output.

Answer. The claim is false because the positive integer $10$ produces $121$ , which is composite.

Check. $11^2=121$ . The input $10$ meets every assumption; a negative input would not disprove this particular claim.

These polynomial results are not in the formula booklet: substitute and justify the counterexample. The same construction settles the opening question:

40^2+40+41=1681=41^2

Forty consecutive prime outputs were a remarkably persuasive pattern, but the next input breaks it. A proof has to reach the cases you have not calculated.

Watch out

Wrong: use an even integer to challenge a claim beginning “if $n$ is odd”. The proposed example fails the assumption. Right: first check the domain and every premise, then show that the conclusion fails.

The next question changes the constant once more. One justified failure is sufficient; there is no need to classify all the other inputs.

Quick Recap

State the domain and assumptions; use $\Leftrightarrow$ only when both directions hold.
For deduction, represent arbitrary integers and connect the resulting algebra to the required property.
For exhaustion, explain why the cases include every possibility.
A counterexample must obey the assumptions and violate the conclusion; one valid failure disproves a universal claim.

Forty prime outputs do not prove the opening claim: $n=40$ gives $1681=41^2$ , so the claim is false.

Last Accessed

Pure Mathematics

Mechanics

Statistics

A1 - Deduction, exhaustion and counterexamples

Claims, domains and logical symbols

Deduction with general integers

Proof by exhaustion

Counterexamples and domain boundaries

Quick Recap

Learn faster with Nova