Proof by Induction & Contradiction — AHL 1.15 Proof by...

SECTION 1

Historical Context & Motivation

Mathematics isn't just about getting the right answer — it's about proving that your answer is right, not just for one case, but for every possible case. For thousands of years, mathematicians have searched for techniques that let them move from "I checked a few examples" to "I know this is always true." Two of the most powerful tools in this arsenal are proof by induction and proof by contradiction. These methods were developed centuries apart, but together they form the backbone of rigorous mathematical reasoning at the HL level.

~300 BCE

Euclid's Elements

Euclid used proof by contradiction (called reductio ad absurdum) to show there are infinitely many prime numbers — a result still celebrated today.

~900 CE

Al-Karaji's Early Induction

Persian mathematician al-Karaji used an implicit form of mathematical induction to prove the binomial theorem and sum formulas for cubes.

1665

Pascal Formalises Induction

Blaise Pascal explicitly described the inductive step when proving properties of his famous triangle, giving induction a clear logical structure.

1889

Peano's Axioms

Giuseppe Peano included the principle of mathematical induction as one of his axioms for the natural numbers, cementing its foundational role in modern mathematics.

Here is the central challenge these techniques address: how do you prove something is true for infinitely many cases? You can't check them all one by one. Induction gives you a systematic way to chain together an infinite sequence of truths, while contradiction lets you prove a statement by showing its opposite leads to an impossibility.

SECTION 2

Core Principles & Definitions

Before diving into the mechanics, let's establish the foundational ideas that make these proof techniques work. Both methods rely on the structure of logic itself, not on any particular area of mathematics, which is what makes them so universally powerful.

The Base Case

In proof by induction, you first verify that the statement is true for the initial value (usually n = 1). This anchors the entire chain of reasoning.

The Inductive Step

Assume the statement holds for some arbitrary natural number k (the inductive hypothesis). Then prove it must also hold for k + 1. This creates the chain reaction.

The Domino Effect

Together, the base case and inductive step guarantee the statement for all natural numbers: n = 1 triggers n = 2, which triggers n = 3, and so on forever.

Negation & Contradiction

In proof by contradiction, you assume the negation of what you want to prove. If logical reasoning from that assumption leads to an impossibility, the original statement must be true.

Law of Excluded Middle

Contradiction works because every mathematical statement is either true or false — there is no middle ground. If "not P" is impossible, then P must be true.

✦ KEY TAKEAWAY

Think of proof by induction like an infinite line of dominoes. The base case is you pushing the first domino over. The inductive step is proving that every domino, when it falls, knocks over the next one. Together, they guarantee every domino in the line will fall. Proof by contradiction is different: it's like showing that a world where the statement is false simply cannot exist — it collapses under its own logical weight.

SECTION 3

Visual Explanation — The Structure of Induction

The diagram shows the three components of an induction proof. The base case (cyan box) verifies P(1). The inductive hypothesis assumes P(k), and the inductive step proves P(k + 1). The bottom chain shows how truth propagates from P(1) through all natural numbers.

As the diagram illustrates, the power of induction lies in its chain structure. You never actually prove the statement for every single natural number individually. Instead, you prove a conditional connection: "if any one case is true, then the next case must also be true." Combined with the base case, this conditional connection cascades outward to cover every natural number, no matter how large.

SECTION 4

Mathematical Framework

Proof by Induction — Formal Structure

PRINCIPLE OF MATHEMATICAL INDUCTION

[P(1) ∧ (∀k ∈ ℕ, P(k) ⟹ P(k+1))] ⟹ ∀n ∈ ℕ, P(n)

P(n) is a proposition depending on a natural number n. If P(1) is true and the truth of P(k) always implies the truth of P(k + 1), then P(n) is true for every natural number n.

In IB exam questions, you'll typically encounter induction proofs for three categories: summation formulas (like 1 + 2 + 3 + ··· + n = n(n + 1)/2), divisibility statements (like "6ⁿ − 1 is divisible by 5"), and formulas involving derivatives or sequences. The structure is always the same three steps, regardless of what you're proving.

Proof by Contradiction — Formal Structure

PROOF BY CONTRADICTION (REDUCTIO AD ABSURDUM)

(¬P ⟹ ⊥) ⟹ P

¬P is the negation of the statement P. The symbol ⊥ represents a logical contradiction (something impossible). If assuming ¬P leads to a contradiction, then P must be true.

In a proof by contradiction, you start by writing "Assume, for the sake of contradiction, that..." and then state the opposite of what you want to prove. You then use valid logical steps until you arrive at something impossible — such as a number being both even and odd, or a fraction in lowest terms that can be simplified further. This impossibility proves your assumption was wrong, so the original statement is true.

CLASSIC EXAMPLE — IRRATIONALITY OF √2

Assume √2 = a/b where gcd(a, b) = 1 → 2b² = a² → a is even → a = 2c → 2b² = 4c² → b² = 2c² → b is even → contradiction with gcd(a, b) = 1

Both a and b turn out to be even, contradicting the assumption that a/b is in lowest terms (gcd = 1). Therefore √2 is irrational.

⚠️ IB Exam Tip

On the IB exam, you must include a concluding statement for both types of proof. For induction, write: "Since P(1) is true and P(k) true ⟹ P(k + 1) true, by the principle of mathematical induction, P(n) is true for all n ∈ ℕ." For contradiction, write: "This is a contradiction, therefore the original assumption is false, and P is true." Missing this conclusion costs marks.

SECTION 5

Detailed Breakdown — Types & Strategies

Not all induction and contradiction proofs look the same. Understanding the common types you'll encounter on the IB exam — and the strategies for each — will help you approach problems efficiently. The diagram below organises the key proof types you need to know.

This classification shows the three main subtypes for each proof technique. Induction (left column) is used when proving a statement for all natural numbers. Contradiction (right column) is used when showing something is impossible or does not exist in a certain form.

When tackling an induction problem, the most challenging part is usually the algebraic manipulation in the inductive step. For summation proofs, this means adding the (k + 1)th term to the assumed formula for k and simplifying. For divisibility proofs, the trick is often to rewrite the expression for k + 1 in terms of the expression for k, plus a multiple of the divisor. Practicing these manipulations is the key to building confidence.

SECTION 6

Worked Examples

Example 1: Proof by Induction — Summation Formula

Prove by mathematical induction that for all n ∈ ℕ:

STATEMENT TO PROVE

1 + 2 + 3 + ··· + n = n(n + 1) / 2

This is the sum of the first n natural numbers.

Induction Proof: Sum of Natural Numbers

Step 1 — Base Case (n = 1)When n = 1, the left-hand side (LHS) is simply 1. The right-hand side (RHS) is 1(1 + 1)/2 = 1(2)/2 = 1. Since LHS = RHS = 1, the base case holds.

P(1) is true ✓

Step 2 — Inductive HypothesisAssume that P(k) is true for some arbitrary k ∈ ℕ. That is, assume: 1 + 2 + 3 + ··· + k = k(k + 1)/2.

Assume P(k): Σ from r=1 to k of r = k(k+1)/2

Step 3 — Inductive Step (prove P(k+1))We need to show that 1 + 2 + ··· + k + (k + 1) = (k + 1)(k + 2)/2. Starting from the LHS of P(k + 1), we write: 1 + 2 + ··· + k + (k + 1) = [k(k + 1)/2] + (k + 1), where we've used the inductive hypothesis to replace the first k terms. Now factor out (k + 1): = (k + 1)[k/2 + 1] = (k + 1)(k + 2)/2. This is exactly the RHS of P(k + 1).

P(k) true ⟹ P(k+1) true ✓

Step 4 — ConclusionSince P(1) is true and P(k) true implies P(k + 1) true, by the principle of mathematical induction, the statement is true for all n ∈ ℕ.

∴ 1 + 2 + ··· + n = n(n+1)/2 for all n ∈ ℕ

Example 2: Proof by Contradiction — √2 is Irrational

Contradiction Proof: Irrationality of √2

Step 1 — Assume the NegationAssume, for the sake of contradiction, that √2 is rational. Then √2 = a/b where a, b ∈ ℤ, b ≠ 0, and gcd(a, b) = 1 (the fraction is in lowest terms, meaning a and b share no common factors).

Assume √2 = a/b with gcd(a,b) = 1

Step 2 — Square Both Sides and DeduceSquaring both sides: 2 = a²/b², so a² = 2b². This means a² is even (it's a multiple of 2). Since the square of an odd number is always odd, a itself must be even. So we can write a = 2c for some integer c.

a² = 2b² → a is even → a = 2c

Step 3 — Substitute and Find a Second Even FactorSubstituting a = 2c into a² = 2b²: (2c)² = 2b², so 4c² = 2b², which gives b² = 2c². By the same reasoning as before, b² is even, so b must also be even.

b² = 2c² → b is also even

Step 4 — Identify the ContradictionBoth a and b are even, which means they share a common factor of 2. But we assumed gcd(a, b) = 1, meaning they share no common factors. This is a contradiction.

Contradiction: gcd(a,b) ≥ 2 but assumed gcd(a,b) = 1

Step 5 — ConclusionSince the assumption that √2 is rational leads to a contradiction, the assumption must be false. Therefore, √2 is irrational.

∴ √2 is irrational ∎

SECTION 7

Induction vs. Contradiction — When to Use Which

Both induction and contradiction are tools for establishing truth, but they're suited to very different types of problems. Understanding when to reach for each technique is one of the most important skills you'll develop in HL Mathematics.

Comparison of the two proof techniques covered in AHL 1.15

Feature	Proof by Induction	Proof by Contradiction
Best used when	The statement involves all natural numbers (or all integers ≥ some base)	You need to show something is impossible or doesn't exist in a certain form
Logical structure	Direct: build truth from base → k → k+1	Indirect: assume the opposite, derive impossibility
Common IB topics	Summation formulas, divisibility, derivatives, inequalities	Irrationality (√2, log₂3), infinitude of primes
Main challenge	Algebraic manipulation in the inductive step	Choosing the right approach after assuming ¬P
Required conclusion	"By PMI, true for all n ∈ ℕ"	"This is a contradiction, ∴ P is true"

🔧 CHOOSING YOUR TOOL

Think of it this way: induction is like climbing a ladder — you check the first rung, then show each rung connects to the next. It's constructive and forward-moving. Contradiction is like a detective eliminating the only other suspect — you show the alternative is impossible, so your conclusion must be true. If the problem says "for all n ∈ ℕ, prove…", try induction first. If it says "prove that X is irrational" or "prove that no Y exists", reach for contradiction.

SECTION 8

Connections to Advanced Mathematics

The techniques you learn in AHL 1.15 are not just exam content — they are the foundation of how mathematicians at every level establish truth. Understanding where these methods lead can help you appreciate why the IB syllabus treats them with such importance.

How AHL 1.15 connects to university-level proof methods

AHL 1.15 (What You Learn Now)	University & Beyond
Proof by induction on ℕ	Strong induction: assume P(1), P(2), …, P(k) are all true, then prove P(k+1). Also structural induction on trees, graphs, and formal languages.
Simple contradiction (√2, primes)	Used in real analysis (e.g., Cantor's proof that the reals are uncountable), topology, and abstract algebra.
Three-step structure (base, hypothesis, step)	Transfinite induction extends the method beyond natural numbers to ordinal numbers — a key tool in set theory.
Law of excluded middle (P or ¬P)	In constructive mathematics and intuitionism, this law is not accepted — leading to fundamentally different proof systems.

If you continue to study mathematics at university, you'll encounter these proof techniques constantly — in courses like real analysis, abstract algebra, and number theory. The ability to write a clean, logical proof is one of the most transferable skills mathematics can give you, and the work you do in AHL 1.15 is your first serious training ground for it.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

A student attempts a proof by induction but omits the base case. They successfully show that P(k) ⟹ P(k + 1) for all k ∈ ℕ. Is the proof valid? Explain why or why not, using the domino analogy.

PROBLEM 2 — BASIC CALCULATION

Prove by mathematical induction that for all n ∈ ℕ: 1² + 2² + 3² + ··· + n² = n(n + 1)(2n + 1) / 6.

PROBLEM 3 — INTERMEDIATE

Prove by induction that 6ⁿ − 1 is divisible by 5 for all n ∈ ℕ (i.e., 5 | (6ⁿ − 1)).

PROBLEM 4 — APPLIED

Prove by contradiction that log₂ 3 is irrational.

PROBLEM 5 — CRITICAL THINKING

Prove by contradiction that there are infinitely many prime numbers. (Hint: consider the number N = p₁ × p₂ × ··· × pₖ + 1, where p₁, p₂, …, pₖ are assumed to be all the primes.)

SUMMARY

Lesson Summary

Proof by induction allows you to prove a statement P(n) for all natural numbers using a base case (verify P(1) is true) and an inductive step (show that P(k) true implies P(k + 1) true). The key challenge lies in the algebraic manipulation required to transform the expression for k + 1 into the desired form. Common applications include summation formulas, divisibility statements, and formulas for derivatives or sequences.

Proof by contradiction works by assuming the negation of what you want to prove and deriving a logical impossibility. This relies on the law of excluded middle — a statement is either true or false. Classic IB examples include proving the irrationality of √2 and the infinitude of primes. For both techniques, always remember to include a clear concluding statement — the IB marking scheme specifically awards marks for this.