Pure mathematics

Proof: Deduction, Exhaustion, Counter-example, and Contradiction

Year 12 · Year 13

✓By the end of this lesson students will be able to construct and follow proofs by deduction.
✓By the end of this lesson students will be able to apply proof by exhaustion for statements with a finite number of cases.
✓By the end of this lesson students will be able to disprove statements using a counter-example.
✓By the end of this lesson students will be able to construct and follow proofs by contradiction.

Key concepts

Proof by Deduction

Proof by deduction involves starting from known facts, axioms, or previously proven theorems and using a sequence of logical steps to arrive at the desired conclusion. Each step must be justified and follow logically from the preceding steps or established truths. This is the most common form of mathematical proof.

Proof by Exhaustion (Proof by Cases)

Proof by exhaustion, also known as proof by cases, is a method used when a statement can be broken down into a finite, manageable number of distinct cases. The statement is then proven true for each individual case. If it holds for all possible cases, the statement is proven true overall. This method is only practical when the number of cases is small.

Disproof by Counter-example

To disprove a universal statement (a statement that claims something is true for 'all' or 'every' instance), one only needs to find a single instance for which the statement is false. This single instance is called a counter-example. A counter-example must satisfy the conditions of the statement but contradict its conclusion.

Proof by Contradiction

Proof by contradiction is an indirect method of proof. To prove a statement P, one assumes the negation of P (i.e., 'not P') to be true. Through a series of logical deductions, this assumption is shown to lead to a contradiction (a statement that is logically impossible or contradicts a known fact). Since the assumption 'not P' leads to a contradiction, 'not P' must be false, meaning the original statement P must be true.

Key facts to remember

1Proof by deduction uses a chain of logical reasoning from known facts to a conclusion.
2Proof by exhaustion is suitable only for statements with a finite and small number of cases.
3A single counter-example is sufficient to disprove a universal statement ('for all' or 'every').
4Proof by contradiction begins by assuming the opposite of what you want to prove.
5The negation of 'P implies Q' is 'P and not Q'.
6Rational numbers can be expressed as p/q, where p and q are integers, q ≠ 0, and p/q is in its simplest form.
7An even number can be written as 2k, and an odd number as 2k+1, for some integer k.
8If a number squared is even, then the number itself must be even.

Worked examples

Example 1

Prove by deduction that the sum of two consecutive odd numbers is always a multiple of 4.

ILet the first odd number be represented by 2n + 1, where n is an integer.

IIThe next consecutive odd number will then be (2n + 1) + 2 = 2n + 3.

IIIThe sum of these two consecutive odd numbers is (2n + 1) + (2n + 3).

IVSum = 4n + 4.

VFactorise the sum: Sum = 4(n + 1).

VISince n is an integer, (n + 1) is also an integer. Therefore, 4(n + 1) is a multiple of 4.

VIIThus, the sum of two consecutive odd numbers is always a multiple of 4.

Answer

The sum is 4(n+1), which is a multiple of 4.

Ensure you define your variables clearly at the start of the proof.

Example 2

Prove by exhaustion that for any integer n such that 1 ≤ n ≤ 4, the expression n² + n + 1 is an odd number.

IWe need to test each integer value of n from 1 to 4.

IICase 1: n = 1

III1² + 1 + 1 = 1 + 1 + 1 = 3. 3 is an odd number.

IVCase 2: n = 2

V2² + 2 + 1 = 4 + 2 + 1 = 7. 7 is an odd number.

VICase 3: n = 3

VII3² + 3 + 1 = 9 + 3 + 1 = 13. 13 is an odd number.

VIIICase 4: n = 4

94² + 4 + 1 = 16 + 4 + 1 = 21. 21 is an odd number.

10Since the expression n² + n + 1 is an odd number for all integers n from 1 to 4, the statement is proven by exhaustion.

Answer

For n=1, 3 (odd); for n=2, 7 (odd); for n=3, 13 (odd); for n=4, 21 (odd). All cases result in an odd number.

This method is only feasible for a small, finite number of cases.

Example 3

Disprove the statement: 'For all real numbers x, if x² > 9 then x > 3'.

IWe need to find a single real number x for which x² > 9 is true, but x > 3 is false.

IIConsider x = -4.

IIICheck the condition: x² = (-4)² = 16. Since 16 > 9, the condition x² > 9 is true.

IVCheck the conclusion: x = -4. Since -4 is not greater than 3, the conclusion x > 3 is false.

VAs we have found a value of x (x = -4) for which the premise is true but the conclusion is false, this serves as a counter-example.

VITherefore, the statement 'For all real numbers x, if x² > 9 then x > 3' is disproven.

Answer

Let x = -4. Then x² = 16, which is > 9. However, -4 is not > 3. Thus, x = -4 is a counter-example.

A single counter-example is sufficient to disprove a universal statement.

Example 4

Prove by contradiction that √2 is irrational.

IAssume, for the sake of contradiction, that √2 is rational.

IIIf √2 is rational, it can be written in the form p/q, where p and q are integers, q ≠ 0, and p/q is in its simplest form (meaning p and q have no common factors other than 1).

IIISo, √2 = p/q.

IVSquaring both sides gives 2 = p²/q².

VRearranging gives p² = 2q².

VIThis implies that p² is an even number. If p² is even, then p must also be an even number (because the square of an odd number is odd).

VIISince p is even, we can write p = 2k for some integer k.

VIIISubstitute p = 2k into the equation p² = 2q²:

9(2k)² = 2q²

104k² = 2q²

11Dividing by 2 gives 2k² = q².

12This implies that q² is an even number. If q² is even, then q must also be an even number.

13So, we have deduced that both p and q are even numbers.

14However, this contradicts our initial assumption that p/q was in its simplest form (i.e., p and q have no common factors other than 1). If both p and q are even, they share a common factor of 2.

15Since our assumption that √2 is rational leads to a contradiction, the assumption must be false.

16Therefore, √2 is irrational.

Answer

Assuming √2 is rational leads to the conclusion that p and q (in √2 = p/q) must both be even, which contradicts the initial assumption that p/q is in its simplest form. Hence, √2 is irrational.

This is a classic A-Level proof. Ensure every step is justified and the contradiction is clearly stated.

Common mistakes

✗Confusing proof by example with a valid proof; showing a statement is true for a few cases does not prove it universally (unless it's proof by exhaustion for all cases).
✗Not clearly stating the initial assumption when using proof by contradiction.
✗Making logical jumps without justification in deductive proofs, especially when manipulating algebraic expressions.
✗Failing to consider all possible cases when attempting a proof by exhaustion.
✗Incorrectly forming the negation of a statement, which is crucial for proof by contradiction.

Exam tips

★Always state the method of proof you are using (e.g., 'Proof by contradiction: Assume...').
★Ensure each step in your proof is logical and clearly justified. Use correct mathematical notation and terminology.
★For proof by contradiction, explicitly state the contradiction you have reached and how it disproves your initial assumption.
★Practise standard proofs, such as the irrationality of √2 or √3, as these often appear in exams.

Ready to practise?

Try a problem on this topic

Snap a photo or type a question — get step-by-step working instantly.

Solve a problem →← Maths curriculum