Proof by deduction and exhaustion

Proof by deduction and exhaustion

Spec A1 · AQA A-Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A proof must work for every case, not just examples; examples cannot prove a statement.
  • Even number 2n2n, odd number 2n+12n+1, consecutive integers n, n+1, n+2n,\ n+1,\ n+2.
  • Use different letters for independent integers, such as 2m2m and 2n2n.
  • Exhaustion splits the possibilities into finite cases, proves each, and shows the cases cover everything.
  • To show a multiple of kk, aim for k(… )k(\dots); to show odd, aim for 2(… )+12(\dots)+1.

The structure of a proof

A proof moves from stated assumptions through justified steps to a conclusion that covers every case.

A proof starts from stated assumptions or known facts and moves through logical steps, each justified, to a conclusion.

It must work for every case covered by the statement, not just examples you have tried.

This subtopic uses two methods: proof by deduction and proof by exhaustion.

  1. 1

    Define symbols

    for example "let nn be an integer"

  2. 2

    Reason in steps

    connect lines with ⇒\Rightarrow, ⇔\Leftrightarrow, "so" or "hence"

  3. 3

    Conclude

    link back to the question, such as "so the sum is odd"

Good presentation of a proof

Does checking that a statement works for n=1,2,3,4,5n=1,2,3,4,5 prove it for all integers?

Proof by deduction

Represent the numbers algebraically, manipulate them, and show the result has the required form.

In proof by deduction you start from known facts and use algebra to reach the result for all values at once.

With nn and mm integers: even is 2n2n, odd is 2n+12n+1, consecutive odd numbers are 2n−12n-1 and 2n+12n+1, a multiple of 3 is 3n3n.

Use different letters for independent integers, such as 2m2m and 2n2n for two even numbers.

  1. 1

    Represent with algebra

    even 2n, odd 2n + 1, consecutive n, n + 1, n + 2

  2. 2

    Manipulate

    expand and factorise

  3. 3

    Show the form of the claim

    k(…) for a multiple of k, 2(…) + 1 for odd

  4. 4

    State the conclusion

    it holds for every integer n

The pattern of a proof by deduction.
  • Even number2n2n
  • Odd number2n+12n+1
  • Consecutive integersn, n+1, n+2n,\ n+1,\ n+2

Worked example

Prove that the sum of three consecutive integers is a multiple of 3.

Worked example

Show that n2+nn^2+n is always even.

Which expression represents any odd number, for integer nn?

Proof by exhaustion

Split the possibilities into a finite number of cases, prove each, and show the cases cover everything.

In proof by exhaustion you check every one of a finite number of cases. Each integer has a remainder when divided by 3, so every integer is 3k3k, 3k+13k+1 or 3k+23k+2.

The last digit of n2n^2 depends only on the last digit dd of nn, because n=10k+dn=10k+d gives n2=10(10k2+2kd)+d2n^2=10(10k^2+2kd)+d^2. Checking d=0,…,9d=0,\dots,9 shows no square ends in 22, 33, 77 or 88.

024680123456789Last digit d of nLast digit of n²
Last digit of a square for each last digit of nn.

Squares modulo 3, using the three cases:

(3k)2=3(3k2),(3k+1)2=3(3k2+2k)+1,(3k+2)2=3(3k2+4k+1)+1.(3k)^2=3(3k^2),\quad(3k+1)^2=3(3k^2+2k)+1,\quad(3k+2)^2=3(3k^2+4k+1)+1.

So every square is 3m3m or 3m+13m+1 for some integer mm.

Can a square number end in 7?

Combining the methods

Factorise first (deduction), then split into cases (exhaustion) to show a divisibility result.

Many proofs use both methods. To prove n3−nn^3-n is divisible by 6, factorise first, then split into cases.

For a sum or product claim, rewrite the result in the form of a multiple, then say why that proves the statement. To show something is odd, aim for 2(… )+12(\dots)+1; to show it is a multiple of kk, aim for k(… )k(\dots).

  1. 1

    Factorise

    n³ − n = (n − 1)n(n + 1)

  2. 2

    Deduction: divisible by 2

    three consecutive integers include an even number

  3. 3

    Exhaustion: divisible by 3

    n = 3k, 3k + 1 or 3k + 2 each give a multiple of 3

  4. 4

    Combine

    2 and 3 share no factor, so it is divisible by 6

Proving that n³ − n is divisible by 6.

Deduction

  • Algebra from known facts
  • Covers all values at once

Exhaustion

  • Split into finite cases
  • Prove each case and show the cases cover everything

Worked example

Prove that n3−nn^3-n is divisible by 6 for every integer nn.

Why is (n−1)n(n+1)(n-1)n(n+1) always divisible by 3?

Try an exam question

Prove that the sum of two consecutive odd numbers is a multiple of 44.

[3 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which expression is always even?

1 mark, marked against the mark scheme

Revision notes