Proof

Welcome to the World of Proof!

Hello future mathematicians! This chapter is one of the most fundamental and rewarding parts of pure mathematics. While calculation chapters focus on how to get an answer, the "Proof" chapter focuses on why that answer (or statement) must be true.

In Pure Mathematics 1 (P1), you built skills in Proof by Deduction. In Unit P2, we take a massive step forward by introducing the powerful technique of Proof by Contradiction. This is the ultimate tool for establishing mathematical certainty. Don't worry if this seems tricky at first—we will break down the logic step-by-step!

Why is Proof Important?

Mathematics relies on absolute certainty. Proof is how we move a statement from being a good guess (a conjecture) to an undeniable truth (a theorem). It ensures the foundations of math are rock-solid.

Section 1: Essential Terminology Review

Before we dive into the methods, let's quickly clarify some terms you must use precisely in your proofs:

• Conjecture: A mathematical statement that is believed to be true, but has not yet been rigorously proven. (Example: "All prime numbers greater than 2 are odd.")
• Theorem: A mathematical statement that has been proven true using valid mathematical arguments (i.e., a proven conjecture).
• Proof: A logical sequence of steps, starting from known facts (axioms or previously proven theorems), that conclusively establishes the truth of a statement.
• Counterexample: A specific case that shows a conjecture or statement is false. Finding just one counterexample is enough to disprove a general statement.

Quick Review Tip: Remember that finding a thousand examples where a statement is true does not prove it. Proof requires showing it holds for all cases.

Section 2: Proof by Deduction (P1 Refresher)

Proof by Deduction is the most common proof method. It involves starting with known facts and logically moving step-by-step until you reach the desired conclusion.

The Process of Deduction (Algebraic Proof)

The key to deduction, especially in P2, is understanding how to represent different types of numbers algebraically:

• Even Number: Represented as \(2n\) (where \(n\) is an integer).
• Odd Number: Represented as \(2n + 1\) or \(2n - 1\) (where \(n\) is an integer).
• Consecutive Integers: \(n\) and \(n+1\).
• Multiples of k: Represented as \(kn\) (where \(n\) is an integer).

Example: Prove that the difference between the squares of two consecutive odd numbers is always a multiple of 8.

Step 1: Set up the variables.
Let the first odd number be \(2n - 1\).
The next consecutive odd number is \((2n - 1) + 2 = 2n + 1\).

Step 2: Form the required expression.
Difference between squares: \((2n + 1)^2 - (2n - 1)^2\)

Step 3: Deduce the result via algebra.
$$ (4n^2 + 4n + 1) - (4n^2 - 4n + 1) $$ $$ 4n^2 + 4n + 1 - 4n^2 + 4n - 1 $$ $$ 8n $$

Step 4: Conclude.
Since the difference simplifies to \(8n\), and \(n\) is an integer, the difference is always a multiple of 8.

Key Takeaway for Deduction

Successful deduction relies on perfect algebraic representation and manipulation. If you cannot simplify the final expression to match the requirement (e.g., finding \(kn\)), your proof is incomplete.

Section 3: Proof by Contradiction (The P2 Core Skill)

This method is often used when direct deduction is too complicated or impossible. It is a powerful technique rooted in logic, and it is a requirement for Pure Mathematics 2.

What is Proof by Contradiction?

Imagine you are a detective trying to prove that a window was not broken by the wind.
Detective’s Logic: "Let's assume the opposite: Assume the window was broken by the wind. If the wind broke it, there would be glass scattered outside. But wait, I only see glass inside! This is impossible. Therefore, the original assumption (that the wind broke it) must be false."

This is exactly how mathematical contradiction works: You assume the statement you want to prove is false, and then you show that this assumption leads to a result that is logically absurd or violates a known mathematical fact. This absurdity is called the contradiction.

Key Term: A Contradiction is a statement that cannot logically be true (e.g., \(0 = 1\), or that an integer is simultaneously even and odd).

The Four Essential Steps for Proof by Contradiction

Follow these steps every time you use this method:

Step 1: Assume the Opposite (The Negation).
State clearly that you are assuming the statement you want to prove is false.

Step 2: Use Deduction.
Logically proceed using algebra and known theorems based on your false assumption.

Step 3: Find the Contradiction.
Show that your logical deduction leads to an impossible or absurd result.

Step 4: Conclude.
State that because the assumption led to a contradiction, the original statement must be true.

Example: Proving \(\sqrt{2}\) is Irrational

This is the most common and important example of proof by contradiction in A-Level mathematics.

Prerequisite Knowledge:
A Rational Number can be written as a fraction \(\frac{a}{b}\), where \(a\) and \(b\) are integers, \(b \neq 0\), and the fraction is in its lowest terms (i.e., \(a\) and \(b\) have no common factors other than 1).

The Proof:

Step 1: Assume the Opposite (Negation)

Assume, for the purpose of contradiction, that \(\sqrt{2}\) is rational.
Therefore, we can write \(\sqrt{2} = \frac{a}{b}\), where \(a\) and \(b\) are integers, \(b \neq 0\), and \(a\) and \(b\) have no common factors.

Step 2: Use Deduction

Square both sides:
$$ 2 = \frac{a^2}{b^2} $$ $$ 2b^2 = a^2 \quad \quad (Equation\ 1) $$ Since \(a^2\) equals \(2\) multiplied by an integer (\(b^2\)), \(a^2\) must be an even number.
If \(a^2\) is even, then \(a\) must also be even.
Since \(a\) is even, we can write \(a\) as \(2k\) (where \(k\) is some integer).

Substitute \(a = 2k\) back into Equation 1:
$$ 2b^2 = (2k)^2 $$ $$ 2b^2 = 4k^2 $$ Divide both sides by 2:
$$ b^2 = 2k^2 $$

Step 3: Find the Contradiction

Since \(b^2\) equals \(2\) multiplied by an integer (\(k^2\)), \(b^2\) must be an even number.
If \(b^2\) is even, then \(b\) must also be even.

We have now proven two things:
1. \(a\) is even.
2. \(b\) is even.

If both \(a\) and \(b\) are even, they must both be divisible by 2. This means they have a common factor of 2.

THIS IS THE CONTRADICTION! In Step 1, we assumed that \(a\) and \(b\) had no common factors (i.e., they were in lowest terms).

Step 4: Conclude

Our initial assumption—that \(\sqrt{2}\) is rational—must be false because it led to the contradiction that \(a\) and \(b\) have common factors, yet they were assumed not to.
Therefore, \(\sqrt{2}\) must be irrational.

!!! COMMON MISTAKE ALERT !!!

If you forget to state in Step 1 that \(a\) and \(b\) have no common factors, your proof is fatally flawed, as you will have nothing to contradict later! This point is essential for the validity of the argument.

Section 4: Other Applications of Proof by Contradiction

Proof by Contradiction can also be used to show that certain types of numbers exist, such as proving there is an infinite number of prime numbers (another classical proof), or to prove properties about sequences and bounds.

Proof Example: The Sum of a Rational and an Irrational Number

Statement: Prove that the sum of a rational number \(x\) and an irrational number \(y\) is always irrational.

Step 1: Assume the Opposite

Assume the sum \(x + y\) is rational.
Let \(z = x + y\). Since \(z\) is rational, we can write \(z = \frac{a}{b}\).
Since \(x\) is rational, we can write \(x = \frac{c}{d}\). (Where \(a, b, c, d\) are integers).

Step 2: Use Deduction

We have \(z = x + y\). We want to isolate the potentially irrational number, \(y\).
$$ y = z - x $$ Substitute the rational representations:
$$ y = \frac{a}{b} - \frac{c}{d} $$ Find a common denominator (\(bd\)):
$$ y = \frac{ad - bc}{bd} $$

Step 3: Find the Contradiction

Since \(a, b, c, d\) are all integers, the numerator \((ad - bc)\) is an integer, and the denominator \((bd)\) is a non-zero integer.
Therefore, \(y\) is the ratio of two integers, which means \(y\) is rational.

THE CONTRADICTION: We were originally given that \(y\) is an irrational number. But our assumption (that \(x + y\) is rational) led us to the conclusion that \(y\) must be rational.

Step 4: Conclude

Since our initial assumption led to a contradiction, the assumption must be false. Therefore, the sum of a rational and an irrational number must be irrational.

Study Tips and Memory Aids

Memory Aid: The P-C Method (For Contradiction)

Think P-C: Presume the opposite, find the Contradiction.

Tip for Algebraic Proofs

Always finish a proof with a concluding sentence that relates your mathematical result back to the original statement. (e.g., "Since the expression simplifies to \(8n\), it is a multiple of 8, Q.E.D. [Quod Erat Demonstrandum - "what was to be shown"].")

Did you know?

The famous Proof by Contradiction that there is an infinite number of prime numbers was first written down by the ancient Greek mathematician Euclid over 2,300 years ago! The same logical structure used in the \(\sqrt{2}\) proof has been central to mathematical thought for millennia.

Quick Review: When to use which Proof?

• Proof by Deduction: Use when you can start from a known fact and simply manipulate the expression (usually algebraically) to get the required result.
• Proof by Contradiction: Use when the statement involves concepts like irrationality, infinity, or when you are proving that something cannot happen. It is essential when a direct deduction is too complex.

Final Encouragement

Proof is about rigour, not speed. Be patient with yourself, clearly define your terms, and always structure your arguments in the four steps provided for contradiction. Once you master this logic, you’ll unlock a higher level of mathematical understanding! Keep practicing!