A: Proof

Overview

$A proof is not a persuasive example or a calculator check. It is a logical guarantee: starting with agreed assumptions, a candidate makes justified steps and reaches a conclusion that must be true in every permitted case. In AQA A-level Mathematics 7357, section 3.2 A1, this means direct deduction, exhaustion, disproof by counter-example and contradiction, including the irrationality of (\sqrt{2}) and the infinitude of primes.$

Proof matters because it is the language that makes algebra, functions, sequences and number theory reliable. AQA can assess it as a short “prove that” item or embed it in a multi-step problem on any paper. The examiner is looking for a clear route from a general assumption such as “let (n) be an odd integer” to a general conclusion, rather than evidence from a few numerical trials. Think of every line as having to answer the question: why is this step allowed?

Listen before you practise:

Key Concepts

1. What counts as a proof?

A statement may be true for several examples without being proved. For instance, (1^2+1), (2^2+2) and (3^2+3) are all even, but checking them only tests three values. To prove the statement for every integer (n), represent all possibilities. The even and odd forms do this neatly:

[
\text{even integer}=2k,\qquad \text{odd integer}=2k+1,\qquad k\in\mathbb Z.
]

A valid proof has four visible features: a stated assumption, connected algebra or logic, a reason that quantities remain in the required set, and an explicit conclusion. Write “Let (n=2k+1), where (k\in\mathbb Z)” rather than merely writing an unexplained expression. This earns credit because it defines the general object under discussion.

2. Proof by deduction: build forwards from the data

Deduction, often called direct proof, begins from what the question gives you. Replace a general condition with its algebraic definition, simplify, then show the required form. If the target is “even”, aim to finish with (2\times\text{integer}). If it is “odd”, aim for (2\times\text{integer}+1). If it is “divisible by 5”, aim for (5\times\text{integer}).

The key examiner test is generality. A candidate who writes “(7^2=49), which is odd” has not proved that every odd square is odd. A candidate who writes ((2k+1)^2=2(2k^2+2k)+1), then identifies the bracket as an integer, has completed the logical bridge.

3. Proof by exhaustion: cover every allowed case

Use exhaustion when the assumptions produce a small, finite and complete list of cases. For parity, the cases are even and odd. For remainders modulo 3, the cases are 0, 1 and 2. State why the list is complete, work through each case, then conclude only after all cases have been dealt with. The method is powerful because no untested possibility remains.

Do not confuse exhaustion with trying a few convenient values. Testing (n=1,2,3) is not exhaustive if (n) can be any positive integer. In contrast, considering the three possible remainders when an integer is divided by 3 really is exhaustive. The set of possible remainders has been restricted to three.

4. Disproof by counter-example: one is enough

To disprove a universal claim such as “all composite numbers have a prime successor”, find one permitted value for which the claim fails. The counter-example must satisfy the condition in the original statement and must make the conclusion false. For example, (8) is composite but (8+1=9) is not prime. Therefore the universal statement is false.

The memory rule is: many examples can support a conjecture; one counter-example destroys it. Never write a counter-example without checking both halves of the statement. If the claim says “for every positive integer”, a negative value is not a valid counter-example.

5. Proof by contradiction: assume the opposite, then force an impossibility

For contradiction, begin by assuming the negation of the result you need. Work logically from that assumption until it clashes with a known fact or with an earlier condition. Then state the contradiction precisely and reject the original opposite assumption.

For irrationality, the standard route is to assume a number is rational and write it as (p/q) in lowest terms, where (p,q\in\mathbb Z) and (q
e0). If the algebra proves both (p) and (q) are even, they share a factor of 2. That contradicts “lowest terms”. The contradiction is not simply “this is impossible”; name the two facts that cannot both hold.

6. Choosing the right method

First inspect the statement. A claim saying “for all integers” is commonly suited to deduction, a finite remainder list or a counter-example if you are asked to disprove it. A claim involving “irrational”, “no such integer” or a stubborn negative statement may invite contradiction. The question can explicitly command a method, so follow that command even if another method might work.

A useful check is to underline the quantifier. For all needs a general proof. There exists needs a valid example. Disprove needs one counter-example. This single habit prevents the frequent error of mistaking numerical evidence for a proof.

7. How proof marks are built

On a short AQA proof, marks are commonly attached to the logical landmarks rather than to the amount of algebra on the page. A clear first line can establish the general case. For example, “Let (n=2k+1), where (k\in\mathbb Z)” gives the examiner a legitimate arbitrary odd integer. Correct transformation earns credit when each line follows from the previous one. The final mark often depends on converting the algebra back into the language of the question: “the bracket is an integer, therefore the expression is odd.”

When checking a proof, read it as a hostile but fair examiner. Has the candidate accidentally assumed what they needed to show? Does every new symbol have a definition? Is a statement about all integers supported by a representation of all integers? Is the conclusion exactly the statement asked, including conditions such as positive, non-zero or in lowest terms? If the answer to any of these is no, repair that line before moving on.

Symbols can make an answer shorter, but words make its logic visible. Use (\therefore) only after the reasoning has been supplied. “(p) is even” is a claim; “(p^2) is even, and an odd square is odd, so (p) is even” is the justified inference. In unfamiliar proofs, this habit of naming the rule is more dependable than trying to copy a remembered pattern.

8. Logical forms worth recognising

The wording of a claim tells you what an answer must achieve. “For every integer (n)” is a universal claim, so your proof must work for an arbitrary integer rather than a selected favourite value. “There exists an integer” only needs one value that meets the stated conditions. “If (P), then (Q)” cannot be proved by showing that (Q) is true for one example; begin from (P) and make (Q) follow. When AQA asks for a disproof, it is usually a signal that a universal claim has a weak point.

Be especially alert to converse errors. From “if an integer is divisible by 4, then it is even”, it does not follow that every even integer is divisible by 4: (2) is a counter-example. Similar statements can look convincing if you read them too quickly. Rewrite the condition in your own words before choosing a method. That ten-second pause protects marks in both proof and algebra questions.

Mathematical Relationships and Language

There is no formula-sheet formula specifically for proof. The following representations and logical implications must be memorised and used accurately:

• (n) even (\Leftrightarrow n=2k), for some (k\in\mathbb Z).
• (n) odd (\Leftrightarrow n=2k+1), for some (k\in\mathbb Z).
• (x) rational (\Leftrightarrow x=p/q), where (p,q\in\mathbb Z), (q
  e0), and preferably (p/q) is in lowest terms for a contradiction proof.
• (a\mid b) means “(a) divides (b)”, so (b=ak) for some integer (k).
• A square is even only if its base is even. Equivalently, the square of an odd integer is odd.

Use (\Rightarrow) for a valid one-way implication and (\Leftrightarrow) only where both directions are true. Avoid using an equals sign between sentences. In a proof, “therefore” and “hence” should follow a justified calculation, not replace one.

Signature AQA Proofs

Why (\sqrt{2}) is irrational

Assume (\sqrt2=p/q) in lowest terms. Squaring gives (p^2=2q^2), so (p^2) is even and therefore (p) is even. Let (p=2k). Substitution gives (q^2=2k^2), so (q) is also even. Both numerator and denominator have factor 2, contradicting lowest terms. The exact words “in lowest terms” and “contradiction” are essential marks of method, not decoration.

Why there are infinitely many primes

Assume there are only finitely many primes (p_1,p_2,\ldots,p_m). Form (N=p_1p_2\cdots p_m+1). When (N) is divided by any listed prime, the remainder is 1. Thus no prime on the supposed complete list divides (N). But (N>1), so it is prime or has a prime factor not on the list. This contradicts completeness. Therefore there are infinitely many primes. Notice that it is not necessary to claim (N) itself is prime.

Practical Applications

Proof is the quality-control system of mathematics. In encryption, a test can show that one message was encoded, but a proof establishes a property for all allowed inputs. In computer algorithms, checking a handful of runs can reveal a bug but cannot guarantee correctness. These applications are reminders of the exam distinction: an example is evidence; a proof is a guarantee.

For revision, practise speaking the structure aloud before writing: assume, represent, transform, justify, conclude. Then cover your notes and reconstruct a proof from its first line. This retrieval practice is more valuable than repeatedly reading a polished model answer.