Proof by deduction, exhaustion and counter-example

Proof by deduction, exhaustion and counter-example

Spec 1.1 · Edexcel A-Level Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • A proof runs from assumptions through logical steps to a conclusion stated in words. Testing examples is not a proof.
  • Deduction: use algebra to prove a result for all cases at once. Even is 2k2k, odd is 2k+12k+1.
  • Exhaustion: split into a finite number of cases and check every one.
  • To disprove a statement you need only one counter-example.
  • Use deduction for all integers or reals, exhaustion for a finite list, a counter-example to disprove.

The structure of a proof

A proof starts from assumptions, takes logical steps where each follows from the one before, and ends with a conclusion in words.

A proof starts from given assumptions, moves through logical steps and ends with a conclusion.

Each step must follow from the one before, and the last line should say what has been proved, such as "so the sum is always odd". Use ⇒\Rightarrow for "implies" and ⇔\Leftrightarrow when the reasoning works both ways.

Testing a few values is not a proof. A proof must work for every case the statement covers. AS needs deduction, exhaustion and disproof by counter-example.

  1. 1

    Assumptions

    what you are given or may take as true

  2. 2

    Logical steps

    each line follows from the one before

  3. 3

    Conclusion

    say in words what has been proved

The shape of every proof

Which is a valid proof that n2n^2 is positive for all real n≠0n\ne0?

Proof by deduction

Start from known facts and use algebra to reach the result for all cases at once, ending with a sentence linking back to the claim.

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

  • Completing the square: n2−6n+10=(n−3)2+1≥1n^2-6n+10=(n-3)^2+1\ge1, so it is positive for all real nn.
  • Divisibility: show the expression equals the divisor times an integer, such as 2n(n+1)2n(n+1) where n(n+1)n(n+1) is even, so the result is a multiple of 4.

Use a different letter for each independent integer, such as 2m2m and 2n2n. End with a sentence linking back to the claim.

−112345672468101214161820xy(3, 1)y = x² − 6x + 10
n² − 6n + 10 = (n − 3)² + 1 has a minimum value of 1 at n = 3, so it is positive for every real n.
  • Even integer2k2k
  • Odd integer2k+12k+1
  • Consecutive integersnn and n+1n+1

Worked example

Prove that the sum of the squares of two consecutive integers is always odd.

Which expression always represents an odd integer, for integer kk?

Deduction with calculus and series

Standard results, such as differentiation from first principles and series sums, are proved by the same method.

The same method proves standard results.

Arithmetic series. Write S=a+(a+d)+⋯+lS=a+(a+d)+\cdots+l and reverse it. Adding the two lines gives 2S=n(a+l)2S=n(a+l), so S=n2(a+l)=n2(2a+(n−1)d)S=\frac n2(a+l)=\frac n2\left(2a+(n-1)d\right).

Geometric series. Sn=a+ar+⋯+arn−1S_n=a+ar+\cdots+ar^{n-1} and rSn=ar+⋯+arnrS_n=ar+\cdots+ar^n. Subtracting gives (1−r)Sn=a(1−rn)(1-r)S_n=a(1-r^n), so Sn=a(1−rn)1−rS_n=\frac{a(1-r^n)}{1-r}.

Dividing by 1−r1-r needs r≠1r\ne1.

  1. 1

    Write the series

    Sn=a+ar+⋯+arn−1S_n=a+ar+\cdots+ar^{n-1}

  2. 2

    Multiply by r

    rSn=ar+⋯+arnrS_n=ar+\cdots+ar^n

  3. 3

    Subtract

    Sn−rSn=a−arnS_n-rS_n=a-ar^n

  4. 4

    Factorise and divide

    Sn=a(1−rn)1−rS_n=\dfrac{a(1-r^n)}{1-r} for r≠1r\ne1

Proof of the geometric series sum

Worked example

Prove from first principles that the derivative of f(x)=x2f(x)=x^2 is 2x2x.

Why does the geometric series proof need r≠1r\ne1?

Proof by exhaustion

Split the possibilities into a finite number of cases and show the statement is true for every one.

In proof by exhaustion you split the possibilities into a finite number of cases and show the statement is true for every case.

Example: prove (p−1)(p+1)(p-1)(p+1) is a multiple of 12 for primes 3<p<253<p<25. The primes are 5, 7, 11, 13, 17, 19, 23, and the chart shows each value divided by 12.

You must (1) list all the cases with none missing, (2) check each, and (3) conclude. It works when the cases are finite or can be reduced to a finite number, such as nn even and nn odd.

0102030402571113171923Prime p(p−1)(p+1) ÷ 12
(p−1)(p+1)÷12(p-1)(p+1)\div12 is a whole number for every prime tested.

To prove n2+nn^2+n is even for every integer nn using exhaustion, which cases do you consider?

Disproof by counter-example

One counter-example is enough: a value that satisfies the conditions but fails the claim.

To show a statement is false you need only one counter-example: a single value that satisfies the conditions but fails the claim.

Example: "for all nn, n2−n+1n^2-n+1 is prime" is untrue because n=5n=5 gives 21=3×721=3\times7.

To prove a statement true you need a general argument. Many examples that work prove nothing: n2+n+41n^2+n+41 is prime for n=1,…,39n=1,\ldots,39, but n=40n=40 gives 1681=4121681=41^2.

051015202345nn² − n + 1
n² − n + 1 is prime for n = 2, 3, 4 (3, 7, 13) but not for n = 5, where it equals 21 = 3 × 7.

To prove true

You need:
A general argument
Note:
Many examples are not enough

To disprove

You need:
One counter-example
Note:
Check it carefully and say why it fails

Worked example

Disprove: "for all positive integers nn, n2−n+1n^2-n+1 is prime".

Which value is a counter-example to "for all positive integers nn, n2>nn^2>n"?

Choosing a method

Use deduction for all integers or reals, exhaustion for a finite list, and a counter-example for a claim you think is false.

A good write-up states the assumptions, shows each logical step, and ends with a conclusion in words. Use ∴\therefore ("therefore") or "hence" to show how lines follow.

If the question says "prove", give a general argument. If it says "show that" with specific numbers, you are checking a particular case.

−1123452468101214xy(2, 3)y = x² − 4x + 7
x² − 4x + 7 = (x − 2)² + 3: the curve never reaches the x-axis, so it is greater than 0 for all x.

Deduction

Use when:
All integers or all real numbers
Example:
x2−4x+7=(x−2)2+3>0x^2-4x+7=(x-2)^2+3>0

Exhaustion

Use when:
A finite list of cases
Example:
primes below 25

Counter-example

Use when:
A claim you think is false
Example:
n=5n=5 for n2−n+1n^2-n+1

Which method suits "prove that x2−4x+7>0x^2-4x+7>0 for all real xx"?

Try an exam question

(a) Prove that the sum of any three consecutive integers is a multiple of 3. (b) Give a counter-example to the statement "the sum of any four consecutive integers is a multiple of 4".

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Which value of nn is a counter-example to the claim?

1 mark, marked against the mark scheme

Revision notes