Welcome to the World of Mathematical Proof!

Ever wondered how mathematicians can be 100% certain that something is true? They don't just "guess" or "check a few numbers" — they use proof. In this chapter, you will learn the art of building an unbreakable logical argument. Think of yourself as a detective or a lawyer; you are going to take known facts and use them to reveal an undeniable truth.

Don't worry if this seems a bit abstract at first! Proof is like a puzzle. Once you learn the "rules of the game" and a few handy tricks, you’ll find it’s one of the most satisfying parts of A Level Maths.

Prerequisite Checklist: Knowing Your Numbers

Before we start, let's quickly review the types of numbers you'll be working with:

  • Integers: Whole numbers (..., -2, -1, 0, 1, 2, ...). Often represented by the letter \(n\) or \(m\) in proofs.
  • Rational Numbers: Numbers that can be written as a fraction \(\frac{p}{q}\) where \(p\) and \(q\) are integers (and \(q \neq 0\)).
  • Irrational Numbers: Numbers that *cannot* be written as a simple fraction (like \(\sqrt{2}\) or \(\pi\)).
  • Real Numbers: All possible numbers on a continuous number line (includes both rational and irrational).

1. The Language of Logic (Connectives)

To write a good proof, we use special symbols called logical connectives. These are the "glue" that holds your argument together.

\(\Rightarrow\) (Implication)

This means "implies" or "if... then".
Example: Being a cat \(\Rightarrow\) having whiskers. (If it is a cat, then it has whiskers).

\(\equiv\) (Identity)

This means "is identically equal to". It’s stronger than a normal equals sign. It means the two sides are the same for every possible value of \(x\).
Example: \(2(x + 1) \equiv 2x + 2\).

\(\Leftrightarrow\) (Equivalence)

This means "if and only if" (often shortened to "iff"). This is used when the logic works perfectly in both directions.
Example: A polygon has three sides \(\Leftrightarrow\) it is a triangle.

Quick Review Box:
\(\Rightarrow\) Logic goes one way.
\(\Leftrightarrow\) Logic goes both ways.

2. Proof by Deduction

This is the most common type of proof. You start with known facts or assumptions and use algebraic steps to reach a conclusion.

How to do it (Step-by-Step):

1. Define your variables: Use \(n\) or \(m\) for integers.
2. Set up the expression: For example, use \(2n\) for an even number and \(2n + 1\) for an odd number.
3. Do the algebra: Expand brackets or factorise.
4. Conclude: Show that your result matches what you were trying to prove.

Example: Prove that the sum of any two odd numbers is even.
Step 1: Let the two odd numbers be \(2n + 1\) and \(2m + 1\).
Step 2: Add them: \((2n + 1) + (2m + 1) = 2n + 2m + 2\).
Step 3: Factorise: \(2(n + m + 1)\).
Step 4: Conclusion: Since the result is a multiple of 2, it must be even. (Proof finished!)

Key Takeaway: In deduction, your algebra must show that the statement is true for all possible numbers, not just a few you picked!

3. Proof by Exhaustion

Sometimes, algebra is too tricky, but the number of possibilities is small. Proof by exhaustion means you check every single case separately.

Analogy: Imagine you want to prove all the light switches in your room work. You don't write an equation; you just walk around and flip every single switch!

Example: Prove that \(n^2 + n\) is even for all integers \(n\).
There are only two types of integers: even and odd.
Case 1 (n is even): Let \(n = 2k\). Then \( (2k)^2 + 2k = 4k^2 + 2k = 2(2k^2 + k) \). This is even!
Case 2 (n is odd): Let \(n = 2k + 1\). Then \( (2k+1)^2 + (2k+1) = (4k^2 + 4k + 1) + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1) \). This is also even!
Since it works for both cases, it works for all integers.

Common Mistake: Forgetting to check one of the cases. If you miss a case, your proof isn't "exhausted"!

4. Disproof by Counter-Example

To prove something is true, you need a full argument. But to disprove something (show it is false), you only need one single example where it fails.

Did you know? This is like the "Black Swan" theory. For centuries, people in Europe thought all swans were white. To prove them wrong, someone just had to find one black swan.

Example: Disprove the statement "All prime numbers are odd."
Counter-example: The number 2.
2 is a prime number, but it is even. Therefore, the statement is false.

Quick Review Box:
Finding 1,000 examples where a rule works does NOT prove it.
Finding 1 example where it fails DOES disprove it.

5. Proof by Contradiction

This is a "backwards" way of proving things. It is very powerful! You start by assuming the statement is FALSE, and then show that this assumption leads to something impossible (a contradiction).

The Logic Flow:

1. Assume the opposite of what you want to prove.
2. Follow the logical steps until you hit a "crash" (e.g., you find that \(1 = 0\) or a number is both even and odd).
3. Conclude that because your assumption led to nonsense, the original statement must be true.

Required Proof 1: \(\sqrt{2}\) is Irrational

Don't worry if this seems tricky at first, it's a classic!
1. Assume the opposite: Assume \(\sqrt{2}\) is rational. This means \(\sqrt{2} = \frac{a}{b}\) where the fraction is in its simplest form (no common factors).
2. Square both sides: \(2 = \frac{a^2}{b^2}\), so \(a^2 = 2b^2\).
3. Logic: This means \(a^2\) is even, so \(a\) must be even. Let \(a = 2k\).
4. Substitute: \((2k)^2 = 2b^2 \Rightarrow 4k^2 = 2b^2 \Rightarrow 2k^2 = b^2\).
5. The Crash: This means \(b^2\) is even, so \(b\) must be even.
6. The Contradiction: If \(a\) and \(b\) are both even, the fraction \(\frac{a}{b}\) wasn't in simplest form! This contradicts our first step.
7. Conclusion: Therefore, \(\sqrt{2}\) must be irrational.

Required Proof 2: There are infinitely many prime numbers

1. Assume the opposite: There is a finite list of primes: \(P_1, P_2, ..., P_n\).
2. Create a new number: Multiply them all together and add 1. Let \(N = (P_1 \times P_2 \times ... \times P_n) + 1\).
3. The Crash: If you divide \(N\) by any of the primes on our "complete" list, you will always get a remainder of 1.
4. The Contradiction: This means either \(N\) is prime itself, or it has a prime factor that isn't on our list.
5. Conclusion: Our list wasn't complete. There will always be more primes!

Key Takeaway: Contradiction is like saying, "If I'm not wearing a coat, I should be cold. I'm not cold, so I must be wearing a coat."

Summary Checklist

Can you:
- Use \(\Rightarrow\) and \(\Leftrightarrow\) correctly?
- Set up a proof using \(2n\) and \(2n+1\) for deduction?
- Split a problem into "Even" and "Odd" cases for exhaustion?
- Find a single counter-example to kill a false claim?
- Explain why \(\sqrt{2}\) is irrational using contradiction?

You've got this! Proof is all about practice. Try writing these out a few times until the logic feels like second nature.