Structure of proof and proof by exhaustion

Structure of proof and proof by exhaustion

Spec 1.1–2 · Edexcel International A Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A proof runs from assumptions through justified steps to a clear conclusion.
  • A few examples that agree with a statement do not prove it.
  • Proof by exhaustion checks every possible case, so it needs a finite number of cases.
  • List every case, check each one, then conclude in words.
  • It cannot prove a statement about all integers.

What a proof is

A proof is a logical argument from given assumptions, through justified steps, to a conclusion that matches the claim.

State what is proved and the numbers it applies to, state any assumptions, show each step, and finish with a conclusion in words that links back to the claim.

To prove a statement for a set of cases, you must deal with every case in the set.

  1. 1

    State the claim

    and the numbers it applies to

  2. 2

    Assumptions

    state what you are given or using

  3. 3

    Logical steps

    each one justified

  4. 4

    Conclusion

    in words, matching the claim

The structure of a proof

Three examples agree with a statement. Is it proved?

Proof by exhaustion

Check every possible case and show the statement is true in each; this works only for a finite number of cases.

List every case allowed by the conditions, check each, and conclude that the statement is true because it holds in every case.

If even one case fails, the statement is false, and the failing case shows why.

  1. 1

    List every case

    allowed by the conditions

  2. 2

    Check each case

    show the working

  3. 3

    Conclude

    true because it holds in every case

Method for proof by exhaustion

When can proof by exhaustion be used?

Example: sums of odd integers

List every pair, work out each sum, and conclude that all are divisible by 22.

Because x+y=y+xx+y=y+x, you may list each unordered pair once, but say that you are doing so.

02468101+11+31+53+33+55+5PairSum
The sum of every pair of odd positive integers less than 7: 2, 4, 6, 6, 8, 10. Every sum is divisible by 2.

Sum

11 and 11:
2
11 and 33:
4
11 and 55:
6
33 and 33:
6
33 and 55:
8
55 and 55:
10

Divisible by 2?

11 and 11:
Yes
11 and 33:
Yes
11 and 55:
Yes
33 and 33:
Yes
33 and 55:
Yes
55 and 55:
Yes
All odd positive integers less than 7.

Worked example

Prove that if xx and yy are odd positive integers less than 77, then x+yx+y is divisible by 22.

How many unordered pairs are there when x,y∈{1,3,5}x,y\in\{1,3,5\}?

Example: evaluating an expression

Set out a table showing the calculation for each case, then state the conclusion in context.

Show the working for each case, not just the answer. This convinces the examiner that every case has been done.

05101520253012345nn² + n
n² + n for n = 1 to 5 gives 2, 6, 12, 20, 30. Every value is even.

n2+nn^2+n

n=1n=1:
2
n=2n=2:
6
n=3n=3:
12
n=4n=4:
20
n=5n=5:
30

Even?

n=1n=1:
Yes
n=2n=2:
Yes
n=3n=3:
Yes
n=4n=4:
Yes
n=5n=5:
Yes

Worked example

Prove that for every integer nn with 1≤n≤51\le n\le5, n2+nn^2+n is even.

What is n2+nn^2+n when n=6n=6?

Limits of exhaustion

It cannot prove a statement about all integers: there are infinitely many cases and you cannot check them all.

Checking n=3,5,7,9n=3,5,7,9 shows n2−1n^2-1 is a multiple of 88 for those values only. It says nothing about n=11n=11.

A single failing case is enough to show a statement false: n2+n+11n^2+n+11 is prime for n=0,…,9n=0,\dots,9, but n=10n=10 gives 121=112121=11^2.

020406080100120012345678910nn² + n + 11
n² + n + 11 is prime for n = 0 to 9 (11, 13, 17, 23, 31, 41, 53, 67, 83, 101), but n = 10 gives 121 = 11², so the statement is false.

Can prove

  • A finite list of cases
  • Every case is checked

Cannot prove

  • All integers
  • Infinitely many cases

n2+n+11n^2+n+11 is prime for n=0n=0 to 99. What does n=10n=10 show?

Try an exam question

Prove, by exhaustion, that n3−nn^3-n is divisible by 66 for every integer nn with 2≤n≤52\le n\le5.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which of the following is needed for a proof by exhaustion of S?

1 mark, marked against the mark scheme

Revision notes