Maths › Proof › The structure of proof: deduction and exhaustion

The structure of proof: deduction and exhaustion

Checking a thousand examples proves nothing. A general argument can settle infinitely many cases in three lines. This lesson is about what a proof actually is, and about the two methods this course requires, deducing a result in general and checking a complete list of cases.

Year 12-13EDEXCEL 9MA0 1.1

IN THIS TOPIC

  • Set a proof out properly, from stated assumptions through checkable steps to a conclusion.
  • Prove statements by deduction and by exhaustion, and choose the method that suits the claim.

COMMON MISCONCEPTION

Checking a statement for the first few numbers proves it.

What counts as a proof

Try a claim on a handful of numbers and it may work every time. That is evidence. Evidence is not proof. A proof starts from given assumptions, things already agreed, moves through logical steps that anybody can check, and ends at a conclusion that must then hold in every case the claim covers. Examples take the cases one at a time. A proof takes all of them at once, and that is the difference between evidence and proof.

The shape of a proof: agreed assumptions feed logical steps to a conclusion holding in every case, while checking examples only samples a fewassumptionslogical stepsconclusionagreed by allcheckable stepstrue in every casechecking examples samples a few cases; a proof covers them allone counter example, though, is enough to sink a claim for good
FIG. 1The shape every proof shares. Assumptions feed the logical steps, and the steps force the conclusion. No amount of example-checking substitutes for that chain.

What makes a general argument possible is algebraic naming. Any even number is 2n for some integer n, and any odd number is 2n + 1. Consecutive integers are n and n + 1. Name the family, argue about the letter, and every member of the family is dealt with in one go. Exams also ask you to choose the method, so both of the two below need to be automatic.

Proof by deduction

Deduction argues in general, and the standard technique for it in this course is completing the square. The standard example asks you to show that n2 − 6n + 10 is positive for every value of n.

WORKED EXAMPLE

Always positive, in two lines

Prove that n2 − 6n + 10 > 0 for all values of n.

Complete the square. n2 − 6n + 10 = (n − 3)2 + 1.

A square is never negative, so (n − 3)2 ≥ 0, and (n − 3)2 + 1 is therefore at least 1. ∎

Look at what did the work. Rewriting the expression made its sign visible. Not one number was tested, and yet every number is covered, negatives and fractions included.

Completing the square: n squared minus 6n plus 10 is bracket n minus 3 squared plus 1, never below 1, so it is positive for every nn = 3lowest value: 1(n − 3)² + 1 never drops below 1
FIG. 2The picture behind the algebra. The parabola of n² − 6n + 10, computed, never dips below its minimum value of 1 at n = 3. The completed square is that picture written in symbols.

GUIDED PRACTICE

Odd times odd

Prove that the product of any two odd numbers is odd, before opening the working.

Show the working

Name the family. Two odd numbers can be written 2m + 1 and 2n + 1 for integers m and n.

(2m + 1)(2n + 1) = 4mn + 2m + 2n + 1 = 2(2mn + m + n) + 1.

That is 2 × (an integer) + 1, which is what odd means. ∎ One expansion and one regrouping. Most of the difficulty sits in the naming at the start.

Proof by exhaustion

Some claims cover only finitely many cases, and then the bluntest method available is watertight. Check every case. Exhaustion is valid only when the list of cases is complete, so open by saying why your list leaves nothing out.

WORKED EXAMPLE

Every prime between 3 and 25

Given that p is a prime number with 3 < p < 25, prove by exhaustion that (p − 1)(p + 1) is a multiple of 12.

The primes strictly between 3 and 25 are 5, 7, 11, 13, 17, 19 and 23, and there are no others.

Taking each in turn, (p − 1)(p + 1) comes out as 24, 48, 120, 168, 288, 360 and 528.

Dividing those by 12 gives 2, 4, 10, 14, 24, 30 and 44, all whole. Every case there is has now been checked. ∎

Exhaustion does not need the cases to be individual numbers. Split the integers into types, even and odd being the usual pair, then deal with each type generally. That is still exhaustion, and it is the standard route to a fact about all the integers when one algebraic form will not stretch to cover them.

INDEPENDENT PRACTICE

Squares, sorted by remainder

Prove that every square number is either a multiple of 4 or one more than a multiple of 4.

Show the working

Every integer is even or odd, and those two cases exhaust the possibilities.

Even. (2n)2 = 4n2, a multiple of 4.

Odd. (2n + 1)2 = 4n2 + 4n + 1 = 4(n2 + n) + 1, one more than a multiple of 4. ∎

Two cases, each settled by deduction, together covering every integer. The methods stack. Writing down that the cases are exhaustive because every integer is even or odd is part of the proof and carries a mark.

ASSESSMENT FOCUS

  • State the family before you use it. "Let the numbers be 2m + 1 and 2n + 1, where m and n are integers" is a mark in its own right, and the rest of your argument has nothing to stand on without it.
  • A claim that a quadratic is always positive or always negative means completing the square. A square term plus a positive constant settles the sign for every value at once, in two lines of working.
  • Choose the method from the shape of the claim. Finitely many cases invites exhaustion, and then your list has to be shown complete before you check anything; a claim about all the integers or all the reals needs deduction.
  • Finish with a sentence that answers the claim in the words it was asked in. Arguments that stop at the last line of algebra commonly drop the final mark.

CHECK YOURSELF

Prove that n³ − n is divisible by 6 for every integer n.

Show a hint

Factorise first, then think about what three consecutive integers must contain.

Show the answer

Factorise. n3 − n = n(n2 − 1) = (n − 1)n(n + 1), the product of three consecutive integers.

Any run of three consecutive integers contains at least one even number, so the product is divisible by 2, and exactly one multiple of 3, so the product is divisible by 3.

Divisible by 2 and by 3 means divisible by 6. ∎ Deduction again, using one factorisation and two facts you already knew about consecutive integers.

A proof runs from stated assumptions through checkable steps to a conclusion, and settles every case in one go.

Deduce when the cases never run out. Exhaust when they do.

WORKBOOK

Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.

Question workbook

PDF · 32 KB · print edition · white background

Question workbook

PDF · 32 KB · screen edition · navy

Answer book

PDF · 37 KB · fully worked · navy
8 questions on this topicAnswer them one at a time and mark yourself against the worked answer.Practise this topic

Or read them with their worked answers on the the structure of proof: deduction and exhaustion questions page.

CHECK YOUR PROGRESS

Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.

  • Set a proof out properly, from stated assumptions through checkable steps to a conclusion.
  • Prove statements by deduction and by exhaustion, and choose the method that suits the claim.

Open the full revision checklist to see every objective in the course in one place.