Understand and use the structure of mathematical proof, proceeding from given assumptions through a series of logical steps to a conclusion; use methods of proof, including: Proof by deduction, Proof by exhaustion, Disproof by counter example, Proof by contradiction (including proof of the irrationality of √2 and the infinity of primes, and application to unfamiliar proofs)

Overview

Mathematical proof is the foundation of certainty in mathematics. While science relies on experiments and observations that might be revised later, a mathematical proof establishes a truth that lasts forever. This topic is crucial for achieving top grades at GCSE, as it tests your ability to reason logically, structure an argument, and communicate mathematically.

Proof questions typically appear towards the end of Higher tier papers and are worth 3 to 5 marks. Examiners are not just looking for the final answer; they are assessing the journey you took to get there. You will need to connect algebra, number theory, and logic.

Key Concepts

Concept 1: Proof by Deduction

This is the most common method of proof. You start from known mathematical facts or definitions and use a step-by-step logical argument to reach a conclusion. Each step must follow necessarily from the previous one.

Why it works: By starting with universally accepted truths (like the definition of an even number) and applying valid algebraic operations, the conclusion is guaranteed to be true.

Example: Prove that the sum of any two odd numbers is even.

• Let the two odd numbers be 2m + 1 and 2n + 1 (where m and n are integers).
• Sum = (2m + 1) + (2n + 1)
• Sum = 2m + 2n + 2
• Factorise: Sum = 2(m + n + 1)
• Since m + n + 1 is an integer, 2(m + n + 1) is a multiple of 2, and therefore even. QED.

Concept 2: Disproof by Counter-Example

To prove a statement is true, you must show it works for all cases. But to prove a statement is false, you only need to find one single case where it fails. This is called a counter-example.

Why it works: A universal claim (e.g., "All swans are white") is instantly shattered by a single exception (finding one black swan).

Example: Disprove the statement "For all integers n, n^2 + n + 11 is a prime number."

• Let n = 11.
• 11^2 + 11 + 11 = 121 + 11 + 11 = 143.
• 143 = 11 \times 13, so it is not prime.
• The statement is false.

Concept 3: Proof by Exhaustion

When a statement only applies to a small, finite number of cases, you can prove it by simply checking every single possibility.

Why it works: If there are only 5 possible scenarios, and you verify the statement holds true for all 5, there are no other possibilities left to contradict it.

Example: Prove that no square number ends in 2, 3, 7, or 8.

• Check the last digit of squares for digits 0-9:
• 0^2 = 0
• 1^2 = 1, 9^2 = 81 (ends in 1)
• 2^2 = 4, 8^2 = 64 (ends in 4)
• 3^2 = 9, 7^2 = 49 (ends in 9)
• 4^2 = 16, 6^2 = 36 (ends in 6)
• 5^2 = 25 (ends in 5)
• All cases checked. The possible last digits are 0, 1, 4, 5, 6, 9. Therefore, no square number ends in 2, 3, 7, or 8.

Concept 4: Proof by Contradiction

This is a powerful technique where you assume the opposite of what you want to prove, and show that this assumption leads to a logical impossibility (a contradiction). Since the assumption led to nonsense, the original statement must be true.

Why it works: In logic, a statement must be either true or false. If assuming it is false leads to an impossible situation, then it cannot be false. Therefore, it must be true.

Key Proof: The irrationality of \sqrt{2}

1. Assume \sqrt{2} is rational. So \sqrt{2} = \frac{a}{b}, where a and b are integers with no common factors.
2. Square both sides: 2 = \frac{a^2}{b^2}, so a^2 = 2b^2.
3. This means a^2 is even, which implies a is even. Let a = 2k.
4. Substitute back: (2k)^2 = 2b^2 \Rightarrow 4k^2 = 2b^2 \Rightarrow 2k^2 = b^2.
5. This means b^2 is even, which implies b is even.
6. Contradiction: We assumed a and b had no common factors, but we just proved both are even (they share a factor of 2).
7. Therefore, the assumption was false. \sqrt{2} is irrational.

Key Proof: The infinity of primes

1. Assume there are finitely many primes: p_1, p_2, ..., p_n.
2. Construct a new number N = (p_1 \times p_2 \times ... \times p_n) + 1.
3. N must be prime or have a prime factor.
4. Dividing N by any prime in our list leaves a remainder of 1. So none of the primes in our list divide N.
5. Contradiction: This means there is a prime factor not in our list, but we assumed our list contained all primes.
6. Therefore, there are infinitely many primes.

Mathematical Relationships

When constructing proofs, you must translate English descriptions into algebra:

• An even number: 2n (where n is an integer)
• An odd number: 2n + 1 or 2n - 1
• Consecutive integers: n, n+1, n+2
• Consecutive even numbers: 2n, 2n+2, 2n+4
• Consecutive odd numbers: 2n+1, 2n+3, 2n+5
• A multiple of 3: 3n
• A rational number: \frac{a}{b} (where a, b are integers, $b
  eq 0$)

Practical Applications

While proof might seem abstract, the underlying logic is the foundation of computer science, cryptography, and algorithms. When a programmer writes code to encrypt your bank details, they rely on mathematical proofs about prime numbers to guarantee that hackers cannot easily break the encryption.