P1.1.1 - Structure of mathematical proof

P1.1.1 - Structure of mathematical proof

A proof is a mathematical argument that starts from clear assumptions and reaches a conclusion through logical steps. In this lesson you will learn how Edexcel expects proof to be written, how to choose between the main proof methods, and why one well-chosen argument is stronger than many unchecked examples. The same proof habits will reappear throughout pure mathematics, especially in identities, inequalities, calculus from first principles, sequences, and unfamiliar "show that" questions.

What a proof must do

A mathematical proof is not a calculation with a lucky answer. It is a chain of reasoning in which every step follows from the assumptions, a definition, a known result, or a previous line of working.

Mathematical proof

A mathematical proof is a logically connected argument that proceeds from given assumptions through valid steps to a conclusion.

For Edexcel A Level Mathematics, the structure matters as much as the algebra. A good proof normally has four visible ingredients:

IngredientWhat it looks like in a proof
Assumptions"Let n be an integer", "Suppose p is prime", "Assume for contradiction..."
Valid stepsAlgebra, definitions, parity facts, divisibility facts, or earlier results
Reasoning words"Since", "therefore", "so", "hence", "which contradicts..."
ConclusionA sentence that answers the statement being proved or disproved

The most important distinction is between a universal statement and an existence statement. A statement such as "for all integers n, n^2-n is even" needs a general proof. Checking n=1, n=2, and n=3 is not enough, because the claim is about every integer. By contrast, to disprove a universal statement, one valid counterexample is enough.

For example, testing

n2−nn^2-n

for n=1, 2, and 3 gives 0, 2, and 6, all even. That suggests the statement may be true, but it does not prove it. A proof would say

n2−n=n(n−1).n^2-n=n(n-1).

The integers n and n-1 are consecutive, so one of them is even. Therefore their product is even. Hence n^2-n is even for every integer n.

Notice the shape of the argument: it did not depend on a special value of n. It used the structure of any integer.

Examples can help you find a pattern, but a proof must explain why the pattern must hold under the stated assumptions.

Proof by deduction

Proof by deduction is the most common proof method in this specification. You start from the assumptions and use algebra, definitions, or known facts to force the conclusion.

Proof by deduction

Proof by deduction proves a statement by moving from accepted facts or assumptions through logical steps to the required conclusion.

Deduction is often the right method when the statement contains words such as "for all", "always", "is positive", "is even", "is divisible by", or "is an identity". The proof should work for the general case, not just for selected examples.

Worked example: prove that

n2−6n+10n^2-6n+10

is positive for all real values of n.

The expression is quadratic, so completing the square is useful:

n2−6n+10=(n−3)2+1.n^2-6n+10=(n-3)^2+1.

For every real value of n,

(n−3)2≥0.(n-3)^2 \geq 0.

Therefore

(n−3)2+1≥1.(n-3)^2+1 \geq 1.

So

n2−6n+10>0n^2-6n+10>0

for all real values of n. This is a proof by deduction because the conclusion follows from the general fact that a square is always non-negative.

The final sentence is not decoration. It tells the examiner that the algebra has been connected to the statement being proved.

Proof by deduction Continued

Common error: do not write only "try n=2, 3, 4". That gives evidence, not proof. The algebra with general n is what proves the result for all consecutive integers.

Proof by exhaustion

Proof by exhaustion is used when there are only finitely many possible cases, and every case can be checked. The word "exhaustion" means the proof exhausts the complete list.

Proof by exhaustion

Proof by exhaustion proves a statement by checking every possible case in a finite, complete set of cases.

This method is valid only when the list is complete. If the statement says 1 <= n <= 4, checking n=1,2,3,4 can prove it. If the statement says "for all integers n", checking a few values cannot prove it.

Worked example: given that p is a prime number such that 3 < p < 25, prove by exhaustion that

(p−1)(p+1)(p-1)(p+1)

is a multiple of 12.

First list every prime satisfying the condition:

p=5,7,11,13,17,19,23.p=5,7,11,13,17,19,23.

Now check the expression for every possible value:

p(p-1)(p+1)Multiple of 12?
5$4 \times 6 = 24$Yes
7$6 \times 8 = 48$Yes
11$10 \times 12 = 120$Yes
13$12 \times 14 = 168$Yes
17$16 \times 18 = 288$Yes
19$18 \times 20 = 360$Yes
23$22 \times 24 = 528$Yes

All possible values of p have been checked, and in each case (p-1)(p+1) is a multiple of 12. Therefore, by exhaustion, the statement is true.

There are two proof habits to notice. First, the possible values were listed before the table. Second, the conclusion refers to all possible values, not just the last row.

Disproof by counterexample

A counterexample is a single example that satisfies the assumptions of a statement but makes its conclusion false. It is used to disprove a universal statement.

Counterexample

A counterexample is a valid case that shows a mathematical statement is not always true.

For a counterexample to work, it must fit the conditions in the original claim. If the claim is about prime numbers, your counterexample must use a prime number. If the claim is about positive integers, your counterexample must be a positive integer.

Worked example: disprove the statement

"n^2-n+1 is a prime number for all positive integer values of n."

Try n=5:

n2−n+1=52−5+1=25−5+1=21.n^2-n+1=5^2-5+1=25-5+1=21.

But

21=3×7,21=3 \times 7,

so 21 is not prime. Since n=5 is a positive integer and the expression is not prime, the statement is false.

One counterexample is enough because the original statement claimed "for all". You do not need to find every value for which it fails.

Disproof by counterexample Continued

Common error: choosing a value that breaks the assumption. For this question, p=9 would not be a valid counterexample because 9 is not prime.

Proof by contradiction

Proof by contradiction begins by assuming the opposite of what you want to prove. You then use valid reasoning to reach an impossibility. That impossibility shows that the assumption must have been false, so the original statement must be true.

Proof by contradiction

Proof by contradiction proves a statement by assuming its negation and showing that this assumption leads to a contradiction.

The structure is:

  1. State the opposite assumption.
  2. Reason from that assumption using valid mathematics.
  3. Reach a contradiction with a known fact or with part of the assumption.
  4. Conclude that the opposite assumption is false.

This method is especially useful for statements about irrationality and infinity, because it is often easier to reason from "suppose it is rational" or "suppose there are finitely many" than to build the result directly.

Before proving that sqrt(2) is irrational, we need one parity fact:

If a^2 is even, then a is even.

Why? If a were odd, then a=2k+1 for some integer k, so

a2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1,a^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1,

which is odd. Therefore an even square cannot come from an odd integer.

Worked example: prove by contradiction that sqrt(2) is irrational.

Assume the opposite: suppose sqrt(2) is rational. Then it can be written as a fraction in lowest terms:

2=ab,\sqrt{2}=\frac{a}{b},

where a and b are integers, b \neq 0, and a and b have no common factor greater than 1.

Square both sides:

2=a2b2.2=\frac{a^2}{b^2}.

So

a2=2b2.a^2=2b^2.

This means a^2 is even, so a is even. Let

a=2ka=2k

for some integer k. Substitute this into a^2=2b^2:

(2k)2=2b2.(2k)^2=2b^2.

So

4k2=2b2,4k^2=2b^2,

and hence

b2=2k2.b^2=2k^2.

This means b^2 is even, so b is even.

We have shown that both a and b are even. That contradicts the assumption that a/b was written in lowest terms. Therefore the assumption that sqrt(2) is rational is false, so sqrt(2) is irrational.

The contradiction is not "the answer looks wrong". It is a precise conflict: the fraction was assumed to be in lowest terms, but the reasoning forced numerator and denominator to share a factor of 2.

Infinitely many primes

The other classic contradiction proof in this specification is the proof that there are infinitely many primes. The key idea is to assume a complete finite list exists, then build a number that cannot be accounted for by that list.

Worked example: prove by contradiction that there are infinitely many prime numbers.

Assume the opposite: suppose there are only finitely many primes. List them as

p1,p2,p3,…,pk.p_1, p_2, p_3, \ldots, p_k.

Now form the number

N=p1p2p3⋯pk+1.N=p_1p_2p_3\cdots p_k+1.

The number N is greater than 1, so it is either prime itself or has a prime factor.

Now divide N by any prime on the list. For example, dividing by p_i gives

N=p1p2⋯pk+1.N=p_1p_2\cdots p_k+1.

The product p_1p_2...p_k is divisible by p_i, so N leaves remainder 1 when divided by p_i. Therefore no prime on the list divides N.

If N is prime, then it is a new prime not on the list. If N is not prime, then it has a prime factor, and that prime factor is not on the list. Either way, there is a prime not in the supposed complete list.

This contradicts the assumption that p_1, p_2, ..., p_k included all primes. Therefore there are infinitely many primes.

This proof is short, but each line has a job. The product-plus-one construction is chosen so that every listed prime leaves remainder 1, making the finite list impossible.

Infinitely many primes Continued

Choosing a proof method is part of the skill:

SituationGood method
Prove a general algebraic factDeduction
Prove a statement over a small finite setExhaustion
Disprove an "always" statementCounterexample
Prove an irrationality or infinity resultContradiction

These are guides, not rigid rules. In an unfamiliar proof, first identify the assumptions and the conclusion. Then ask what would be easiest to control: a general algebraic expression, a finite list of cases, one failure, or the consequences of assuming the opposite.

Explain It Back

Use this as a self-explanation check after the section above. It is for diagnosing what you can already explain, not for learning new material from scratch.