Introduction to Formal Proof
At Higher Level, you are expected to construct and evaluate rigorous mathematical arguments — not just calculate answers. This subtopic introduces three major tools of formal proof:
- Proof by mathematical induction — establish a statement for all natural numbers by a domino-like logical chain
- Proof by contradiction — assume the opposite of what you want to prove and derive an impossibility
- Counterexamples — disprove a universal statement with a single specific case
Each method has a precise structure. In IB examinations, marks are awarded for following that structure correctly — not just arriving at the right answer.
In this course, unless otherwise stated. When a statement begins at , this will be specified explicitly in the question.
Proof by induction is most commonly examined on Papers 1 and 2. Proof by contradiction and counterexamples appear most frequently on Paper 3 (the AA HL investigations-style paper), where extended reasoning and multi-step arguments are expected.
What is Proof by Mathematical Induction?
A method of proof used to establish that a statement is true for all natural numbers (or all integers above some base value), by showing it holds for a starting value, and that if it holds for any value , it must also hold for .
The underlying logic is beautifully simple. Imagine an infinite row of dominoes:
If you know the first domino falls (base case), and you know that whenever any domino falls, it knocks over the next one (inductive step) — then every single domino must eventually fall. Mathematical induction works exactly like this.
The key ingredients are:
- Base case — verify for the smallest value in its domain
- Inductive hypothesis — assume is true for an arbitrary in the domain
- Inductive step — prove is true, using the inductive hypothesis
- Conclusion — tie the argument together formally
The inductive step alone is not enough — and the base case alone is not enough. Both are essential. A famous illustration of how an inductive argument can fail is the so-called "all horses are the same colour" paradox: the base case is trivially true (one horse trivially has the same colour as itself), but the inductive step breaks down at the very first use — when moving from to . The argument claims to match colours via an overlapping middle group, but with only two horses there is no overlapping element, so the colour-matching fails entirely. This shows that a flawed inductive step (not just a missing base case) can destroy an entire proof. Always verify both components carefully.