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

The structure of proof: deduction and exhaustion

Checking a thousand examples proves nothing; a good argument covers infinitely many cases in three lines. This lesson is about what a proof actually is, and the two workhorse methods the course leans on: deduce it in general, or check every case there is.

Year 12-13EDEXCEL 9MA0 1.1

IN THIS TOPIC

  • Describe the structure of a proof: assumptions, logical steps, conclusion.
  • Prove statements by deduction, using algebra to cover every case at once.
  • Prove statements by exhaustion, checking a complete list of cases.

WHAT YOU PROBABLY THINK

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 well work every time; that is evidence, and evidence is not proof. A proof is an argument that starts from given assumptions, things already agreed, moves through a series of logical steps, each one checkable, and ends at a conclusion that must then hold in every case the claim covers. The gap between the two is infinite: examples sample cases one at a time, while the argument covers all of them at once.

The shape of a proof: agreed assumptions feed a chain of logical steps that ends at a conclusion holding in every case, while checking examples only ever 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 shared by every proof. Assumptions feed logical steps, and the steps force the conclusion; no amount of example-checking can substitute for the chain.

The tools that make general arguments possible are algebraic names for whole families of numbers. Any even number is 2n for some integer n; any odd number is 2n + 1; consecutive integers are n and n + 1. Write the family, argue about the letter, and every member of the family is dealt with simultaneously. Exams reward choosing the most appropriate method of attack, so both methods below need to be fluent.

Proof by deduction

Deduction is the general-argument method, and the course's favourite instrument for it is completing the square. The standard example: prove 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 therefore (n − 3)2 + 1 ≥ 1 > 0 for every n. ∎

Notice what did the work: rewriting the expression so that its sign became visible. No number was ever tested, yet every number is covered, including every negative and every fraction.

Completing the square shows n squared minus 6n plus 10 equals bracket n minus 3 close bracket squared plus 1, a parabola whose lowest point is 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 in symbols.

YOUR TURN

Odd times odd

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

Show the working

Name the family: any 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.

This is 2 × (an integer) + 1, which is the definition of odd. ∎ The whole proof is one expansion and one regrouping; the skill is naming the numbers well at the start.

Proof by exhaustion

Some claims cover only finitely many cases, and then the bluntest method is airtight: check every case. That is proof by exhaustion, and it is only valid when the list of cases is complete, so a proof by exhaustion should open by saying why the list is the whole list.

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 complete list of primes between 3 and 25 is 5, 7, 11, 13, 17, 19, 23.

In turn: 4 × 6 = 24, 6 × 8 = 48, 10 × 12 = 120, 12 × 14 = 168, 16 × 18 = 288, 18 × 20 = 360, 22 × 24 = 528.

Each of 24, 48, 120, 168, 288, 360, 528 is divisible by 12 (giving 2, 4, 10, 14, 24, 30, 44), so the statement holds for every case there is. ∎

Exhaustion does not need the cases to be individual numbers. Splitting all integers into types, even and odd, say, and dealing with each type generally is also exhaustion, and it is the standard way to prove facts about all integers when one algebraic form will not cover them.

TRY IT UNSEEN

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: the 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 handled by deduction, together covering every integer: the methods stack, and saying "these cases are exhaustive because every integer is even or odd" is part of the proof.

THE EXAM BIT

  • State the family you are naming before you use it: "let the numbers be 2m + 1 and 2n + 1 where m, n are integers". The declaration is worth a mark and the argument collapses without it.
  • For always-positive or always-negative quadratic claims, completing the square is the intended route: a square term plus a positive constant settles the sign for every value at once.
  • A proof by exhaustion must show its list is complete. Open with the full list of cases and say why nothing is missing; then check each case explicitly.
  • End with a conclusion that answers the claim as stated: "so the product of any two odd numbers is odd". An argument that trails off before the conclusion drops the final mark.
  • Choose the method to fit the claim: finitely many cases invites exhaustion; a claim over all integers or all reals needs deduction, possibly split over exhaustive types.

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 both 2 and 3 means divisible by 6. ∎ The proof is deduction, powered by one factorisation and two facts about consecutive integers.

A proof runs assumptions, steps, conclusion, and covers every case at once.

Deduce with algebra when the cases are infinite; exhaust the list when it is finite.

CHECK YOUR PROGRESS

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

  • Describe the structure of a proof: assumptions, logical steps, conclusion.
  • Prove statements by deduction, using algebra to cover every case at once.
  • Prove statements by exhaustion, checking a complete list of cases.

No animated video for this topic yet; these notes stand alone.