Introduction to Proof (HL)
Welcome to one of the most intellectually rewarding parts of the IB Higher Level Mathematics curriculum! Up until now, you have likely used formulas and rules provided to you. In this chapter, we step behind the curtain to learn how those rules are actually established. Proof is the process of using logical steps to show that a mathematical statement is unquestionably true. Think of it like being a lawyer in a high-stakes court case—your job is to provide an argument so solid that no one can doubt your conclusion.
We will cover three powerful tools: Counterexample, Contradiction, and Mathematical Induction.
Quick Note: This topic belongs to the Number and Algebra (HL) section. While you might use techniques from trigonometry or calculus within these proofs, the focus here is on the logical structure of the argument.
1. Use of a Counterexample
In mathematics, many statements claim that something is always true for every single number in a set. To prove such a statement is false, you don't need to write a long essay. You only need to find one single case where the statement does not work. This single case is called a counterexample.
How it works:
If someone says, "All prime numbers are odd," you can simply say, "Wait, \(2\) is a prime number and it is even." Because you found one exception, the entire general statement is proven false.
Example:
Statement: For all \(n \in \mathbb{Z}^+\), \(n^2 + n + 41\) is a prime number.
Investigation:
If \(n = 1\), \(1^2 + 1 + 41 = 43\) (Prime)
If \(n = 2\), \(2^2 + 2 + 41 = 47\) (Prime)
It looks true! But if we test \(n = 41\):
\(41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \times 43\).
Since \(41 \times 43\) has factors other than \(1\) and itself, it is not prime. Therefore, \(n = 41\) is our counterexample, and the statement is false.
Key Takeaway: One "No" is stronger than a million "Yeses" when it comes to disproving a universal claim.
2. Proof by Contradiction
Proof by contradiction is a bit like a detective story. To prove that a statement is true, we start by assuming the statement is false. We then follow the logical consequences of that assumption until we hit a "brick wall"—a mathematical impossibility (a contradiction). Since our logic was sound, the only possible error must have been our initial assumption. Therefore, the original statement must be true!
The Step-by-Step Process:
- Assume the opposite: Start by stating clearly that you are assuming the negation of the proposition.
- Logical Deduction: Use algebra or known facts to work through the consequences.
- Find the Contradiction: Arrive at a result that is clearly impossible (e.g., \(0 = 1\) or saying a number is both even and odd).
- Conclude: State that because of the contradiction, the original statement must be true.
Classic Example: Prove that \(\sqrt{2}\) is irrational.
1. Assume the opposite: Assume \(\sqrt{2}\) is rational. This means it can be written as \(\frac{a}{b}\) where \(a\) and \(b\) are integers with no common factors (the fraction is in simplest form).
2. Square both sides: \(2 = \frac{a^2}{b^2} \implies a^2 = 2b^2\).
3. Deduce: This means \(a^2\) is even, so \(a\) must be even. Let \(a = 2k\).
4. Substitute back: \((2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies 2k^2 = b^2\).
5. The Contradiction: This means \(b^2\) is also even, so \(b\) must be even. But if both \(a\) and \(b\) are even, they have a common factor of \(2\). This contradicts our initial assumption that the fraction had no common factors!
6. Conclusion: Therefore, \(\sqrt{2}\) must be irrational.
Quick Review: Look for words like "irrational" or "no solutions" as hints that contradiction might be the right tool.
3. Proof by Mathematical Induction
Mathematical Induction is used to prove that a statement is true for all positive integers (\(n = 1, 2, 3, \dots\)).
The Domino Analogy:
Imagine an infinite row of dominoes. To prove they will all fall down, you only need to prove two things:
1. The first domino falls.
2. If any domino falls, it will definitely knock over the next one.
The Formal Steps:
Step 1: The Basis Step
Show the statement is true for the first case (usually \(n = 1\)). Check both the Left Hand Side (LHS) and Right Hand Side (RHS).
Step 2: The Assumption (Inductive Hypothesis)
Assume the statement is true for \(n = k\). Write this step out clearly!
Step 3: The Inductive Step
Show that if it is true for \(n = k\), it must be true for \(n = k+1\). This is the "meat" of the proof where you use your assumption from Step 2 to prove the next case.
Step 4: The Conclusion
IB examiners look for a specific concluding sentence. It should look like this:
"Since the statement is true for \(n = 1\), and if true for \(n = k\) it is shown to be true for \(n = k + 1\), then by the principle of mathematical induction, it is true for all \(n \in \mathbb{Z}^+\)."
Example: Sum of first \(n\) integers.
Prove that \(1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\)
1. Basis Step: Let \(n = 1\).
LHS \(= 1\).
RHS \(= \frac{1(1+1)}{2} = \frac{2}{2} = 1\).
LHS = RHS, so true for \(n = 1\).
2. Assumption: Assume true for \(n = k\):
\(1 + 2 + \dots + k = \frac{k(k+1)}{2}\)
3. Inductive Step: Prove true for \(n = k + 1\).
We want to show the sum is \(\frac{(k+1)((k+1)+1)}{2} = \frac{(k+1)(k+2)}{2}\).
LHS \(= (1 + 2 + \dots + k) + (k+1)\)
Substitute our assumption: \(= \frac{k(k+1)}{2} + (k+1)\)
Factor out \((k+1)\): \(= (k+1)[\frac{k}{2} + 1] = (k+1)[\frac{k+2}{2}] = \frac{(k+1)(k+2)}{2}\).
LHS = RHS for \(n = k + 1\).
4. Conclusion: (Insert the standard IB boilerplate conclusion mentioned above).
Common Pitfalls in Induction:
• Forgetting to write down the assumption for \(n=k\).
• Not clearly labeling the Basis Step and the Inductive Step.
• Errors in algebraic manipulation (especially with fractions or factorials).
• Forgetting the final concluding sentence (you can lose 1 or 2 marks just for this!).
Summary Checklist
- Counterexample: Used to prove a statement is false. You only need one!
- Contradiction: Assume the statement is false and find a logical impossibility.
- Induction: Used for sequences, sums, and divisibility involving integers. Remember: Basis \(\rightarrow\) Assumption \(\rightarrow\) Step \(\rightarrow\) Conclusion.
Don't worry if this seems tricky at first! Proof is a new way of thinking. The more you practice the "structure" of these arguments, the more natural they will feel.