Unit 3 Lesson 2

Mathematical Induction

In this lesson, we introduce mathematical induction — a proof method tailored to universal statements about the natural numbers. Induction rests on our first genuine axiom: a foundational principle about \(\mathbb{N}\) that cannot be derived from logic alone.

Learning Objectives

  • State the Principle of Mathematical Induction rigorously

  • Recognise induction as an axiom, not a theorem

  • Identify the base case and the inductive step in an induction proof

  • Formulate the inductive hypothesis correctly

  • Apply induction to prove sum formulas and divisibility results

  • Detect common errors: missing base case, false claim with valid step, and others

Universal Claims About the Natural Numbers

Many of the most important statements in mathematics have the form “for every natural number \(n\), the property \(P(n)\) holds.” Examples abound: every natural number greater than 1 has a prime factor; every sum \(1 + 2 + \cdots + n\) equals \(n(n+1)/2\); every power \(2^n\) is greater than \(n\).

Reductio ad absurdum, introduced in the previous lesson, is in principle a universal-purpose technique: assume the negation, derive a contradiction. But for universal claims indexed by \(\mathbb{N}\), reductio is rarely the most natural tool. The negation \(\exists n \in \mathbb{N},\, \neg P(n)\) does not, in general, give us a concrete \(n\) to work with — only its abstract existence.

For such claims, mathematics has developed a method that exploits the very structure of the natural numbers themselves: mathematical induction.

The Successor Structure of \(\mathbb{N}\)

The natural numbers \(0, 1, 2, 3, \ldots\) are generated from \(0\) by the operation of taking the successor: the successor of \(n\) is \(n + 1\). Every natural number is reached from \(0\) in finitely many successor steps:

\[0 \;\to\; 1 \;\to\; 2 \;\to\; 3 \;\to\; \cdots\]

This is a defining feature of \(\mathbb{N}\): the natural numbers are precisely the values obtainable by starting at \(0\) and applying the successor operation repeatedly. Mathematical induction is the proof method that mirrors this generative structure.

The Intuition: Dominoes

Imagine an infinite row of dominoes, labelled \(0, 1, 2, 3, \ldots\). Two facts together guarantee that every domino will fall:

  1. Domino \(0\) is pushed.

  2. For each \(k\), domino \(k\) is positioned closely enough to domino \(k+1\) that, if domino \(k\) falls, domino \(k+1\) also falls.

From these two conditions, one concludes that every domino falls: domino \(0\) falls by (1); domino \(1\) falls because domino \(0\) fell and (2) applies; domino \(2\) falls because domino \(1\) fell; and so on. Mathematical induction is the rigorous formalisation of this intuition. Condition (1) becomes the base case; condition (2) becomes the inductive step.

The Principle of Mathematical Induction

Let \(P(n)\) be a predicate defined for all natural numbers \(n \geq n_0\), where \(n_0\) is some fixed natural number. If both:

  1. (Base case) \(P(n_0)\) holds; and

  2. (Inductive step) for every \(k \geq n_0\), \(P(k) \to P(k+1)\) holds,

then \(P(n)\) holds for every natural number \(n \geq n_0\).

In symbols:

\[\Big( P(n_0) \;\land\; \forall k \geq n_0,\; P(k) \to P(k+1) \Big) \;\implies\; \forall n \geq n_0,\; P(n)\]

The hypothesis “\(P(k)\)” assumed in the inductive step is called the inductive hypothesis.

Induction is an Axiom

The Principle of Mathematical Induction is an axiom: a foundational statement that we accept as part of what defines the natural numbers. It cannot be derived from the apparatus of logic introduced in Units 1 and 2. The Italian mathematician Giuseppe Peano (1858–1932) gave a precise axiomatisation of \(\mathbb{N}\) in 1889, in which induction figures as one of the defining axioms. To accept the existence of \(\mathbb{N}\) — with its endless chain \(0, 1, 2, 3, \ldots\) and its property that every natural number is reached from \(0\) in finitely many successor steps — is, in essence, to accept the Principle of Induction.

The Principle of Induction is foundational to the natural numbers.

Anatomy of an Induction Proof

To prove a statement “\(P(n)\) holds for every \(n \geq n_0\)” by mathematical induction, one must do the following:

  1. State the predicate \(P(n)\) precisely.

  2. Verify the base case: prove that \(P(n_0)\) holds.

  3. State the inductive hypothesis: assume \(P(k)\) holds for some arbitrary \(k \geq n_0\).

  4. Prove the inductive step: deduce that \(P(k+1)\) holds, using the inductive hypothesis.

  5. Conclude: by the Principle of Mathematical Induction, \(P(n)\) holds for every \(n \geq n_0\).

Both the base case and the inductive step are essential. Omitting either one leaves the proof incomplete — and, as we shall see in this lesson’s critical examination, capable of “proving” statements that are false.

Sum of the First \(n\) Natural Numbers

For every natural number \(n \geq 1\):

\[1 + 2 + 3 + \cdots + n \;=\; \frac{n(n+1)}{2}\]

Proof — Sum of the First \(n\) Natural Numbers

Let \(P(n)\) be the predicate “\(1 + 2 + \cdots + n = n(n+1)/2\).” We proceed by induction on \(n\), with base \(n_0 = 1\).

Base case. For \(n = 1\): the left-hand side is \(1\), and the right-hand side is \(1 \cdot 2 / 2 = 1\). The two sides agree, so \(P(1)\) holds.

Inductive step. Fix an arbitrary \(k \geq 1\) and assume the inductive hypothesis:

\[1 + 2 + \cdots + k \;=\; \frac{k(k+1)}{2}\]

We must prove \(P(k+1)\), namely:

\[1 + 2 + \cdots + k + (k+1) \;=\; \frac{(k+1)(k+2)}{2}\]

Starting from the left-hand side and applying the inductive hypothesis:

\[\begin{aligned} 1 + 2 + \cdots + k + (k+1) &= \frac{k(k+1)}{2} + (k+1) \\ &= (k+1)\left(\frac{k}{2} + 1\right) \\ &= (k+1) \cdot \frac{k+2}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{aligned}\]

This is exactly \(P(k+1)\). Hence \(P(k) \to P(k+1)\) for every \(k \geq 1\).

By the Principle of Mathematical Induction, \(P(n)\) holds for every \(n \geq 1\). \(\blacksquare\)

Sum of the First \(n\) Odd Numbers

For every natural number \(n \geq 1\):

\[1 + 3 + 5 + \cdots + (2n - 1) \;=\; n^2\]

That is, the sum of the first \(n\) odd positive integers is the perfect square \(n^2\).

Proof — Sum of the First \(n\) Odd Numbers

Let \(P(n)\) be the predicate “\(1 + 3 + 5 + \cdots + (2n - 1) = n^2\).” We proceed by induction on \(n\), with base \(n_0 = 1\).

Base case. For \(n = 1\): the left-hand side is \(2 \cdot 1 - 1 = 1\), and the right-hand side is \(1^2 = 1\). They agree, so \(P(1)\) holds.

Inductive step. Fix \(k \geq 1\) and assume \(1 + 3 + \cdots + (2k - 1) = k^2\). We must prove that \(1 + 3 + \cdots + (2k - 1) + (2(k+1) - 1) = (k+1)^2\). The new term added on the left is \(2(k+1) - 1 = 2k + 1\). Applying the inductive hypothesis:

\[1 + 3 + \cdots + (2k - 1) + (2k + 1) \;=\; k^2 + (2k + 1) \;=\; k^2 + 2k + 1 \;=\; (k+1)^2\]

This is \(P(k+1)\), establishing the inductive step.

By the Principle of Mathematical Induction, \(P(n)\) holds for every \(n \geq 1\). \(\blacksquare\)

A Divisibility Result

For every natural number \(n \geq 1\):

\[4 \mid (5^n - 1)\]

That is, \(5^n - 1\) is divisible by \(4\) for every positive integer \(n\).

Proof — Divisibility of \(5^n - 1\) by \(4\)

Let \(P(n)\) be the predicate “\(4 \mid (5^n - 1)\).” We proceed by induction on \(n\), with base \(n_0 = 1\).

Base case. For \(n = 1\): \(5^1 - 1 = 4\), and \(4 \mid 4\). So \(P(1)\) holds.

Inductive step. Fix \(k \geq 1\) and assume \(4 \mid (5^k - 1)\). That is, \(5^k - 1 = 4m\) for some integer \(m\). We must prove \(4 \mid (5^{k+1} - 1)\). Compute:

\[5^{k+1} - 1 \;=\; 5 \cdot 5^k - 1 \;=\; 5 \cdot 5^k - 5 + 4 \;=\; 5(5^k - 1) + 4\]

By the inductive hypothesis, \(5^k - 1 = 4m\), so \(5(5^k - 1) = 20m\). Therefore:

\[5^{k+1} - 1 \;=\; 20m + 4 \;=\; 4(5m + 1)\]

which is divisible by \(4\). Hence \(P(k+1)\) holds.

By the Principle of Mathematical Induction, \(4 \mid (5^n - 1)\) for every \(n \geq 1\). \(\blacksquare\)

Connection to Computer Science

Mathematical induction underlies the way computers solve repetitive tasks. Programs that work by breaking a problem into a smaller version of itself, or by repeating a step many times, can be checked for correctness using induction: the base case verifies the smallest input, and the inductive step verifies that the program preserves correctness when moving from one input size to the next. Without induction, there would be no rigorous way to guarantee that a program produces the right answer for inputs of every possible size.

Exercise 1

For each induction proof outline, identify the correct inductive hypothesis.

a)

Claim: for every \(n \geq 1\), \(1 + 2 + \cdots + n = n(n+1)/2\).

After verifying the base case, what is the inductive hypothesis?

b)

Claim: for every \(n \geq 1\), \(7 \mid 8^n - 1\).

After verifying the base case, what is the inductive hypothesis?

c)

Claim: for every \(n \geq 1\), \(1^2 + 2^2 + \cdots + n^2 = n(n+1)(2n+1)/6\).

After verifying the base case, what is the inductive hypothesis?

Exercise 2

For each induction proof, identify what must be proved in the inductive step.

a)

To prove that for every \(n \geq 1\), \(1 + 2 + \cdots + n = n(n+1)/2\).

Assuming the formula holds for some \(k \geq 1\): What must be proved in the inductive step?

b)

To prove that for every \(n \geq 1\), \(n^2 + n\) is even.

Assuming \(k^2 + k\) is even: What must be proved in the inductive step?

c)

To prove that for every \(n \geq 1\), \(4 \mid 5^n - 1\).

Assuming \(4 \mid 5^k - 1\): What must be proved in the inductive step?

Exercise 3

For each argument, decide whether it is a valid induction proof.

a)

Claim: for every \(n \geq 1\), \(2 + 4 + 6 + \cdots + 2n = n(n+1)\).

Proof: Assume true for \(n = k\): \(2 + 4 + \cdots + 2k = k(k+1)\). Then \(2 + 4 + \cdots + 2k + 2(k+1) = k(k+1) + 2(k+1) = (k+1)(k+2)\). So true for \(n = k+1\). By induction, true for all \(n \geq 1\).

b)

Claim: for every \(n \geq 1\), \(1 + 2 + \cdots + n = n(n+1)/2 + 5\).

Proof: Assume \(1 + 2 + \cdots + k = k(k+1)/2 + 5\). Then \(1 + 2 + \cdots + k + (k+1) = k(k+1)/2 + 5 + (k+1) = (k+1)(k+2)/2 + 5\). By induction, the formula holds for all \(n \geq 1\).

c)

Claim: for every \(n \geq 1\), \(9 \mid 10^n - 1\).

Proof: Base case \(n=1\): \(10 - 1 = 9\), divisible by \(9\). Inductive step: assume \(9 \mid 10^k - 1\). Then \(10^{k+1} - 1 = 10 \cdot 10^k - 1 = 10(10^k - 1) + 9\). By the inductive hypothesis, \(9 \mid 10(10^k - 1)\); also \(9 \mid 9\). Hence \(9 \mid 10^{k+1} - 1\). By induction, the claim holds for every \(n \geq 1\).

Critical Examination

A student is asked to prove the formula:

\[1 + 2 + \cdots + n \;=\; \frac{n(n+1)}{2} + 100 \qquad \text{for every } n \geq 1\]

The student writes:

Inductive step. Assume the formula holds for \(n = k\): \(1 + 2 + \cdots + k = k(k+1)/2 + 100\). Adding \((k+1)\) to both sides:

\[1 + 2 + \cdots + k + (k+1) \;=\; \frac{k(k+1)}{2} + 100 + (k+1) \;=\; \frac{(k+1)(k+2)}{2} + 100\]

So if the formula holds for \(n = k\), it holds for \(n = k+1\). By the Principle of Mathematical Induction, the formula holds for every \(n \geq 1\).

What has gone wrong?

Analysis

The student’s inductive step is mathematically flawless. Yet the formula they have “proved” is plainly false: at \(n = 1\), the left-hand side is \(1\), while the right-hand side is \(1 \cdot 2 / 2 + 100 = 101\). The two sides differ by \(100\). What happened?

The error is the omission of the base case. The Principle of Mathematical Induction has two hypotheses: \(P(n_0)\) and \(\forall k \geq n_0, P(k) \to P(k+1)\). The student established only the second.

Recall the domino intuition. The inductive step ensures that if domino \(k\) falls, then domino \(k+1\) falls. But if no domino has been pushed, none of them falls. The student has correctly arranged the dominoes; they have not pushed the first one. The arrangement, by itself, sets nothing in motion.

This explains why the “proof” reaches a false conclusion. From the (true) implications \(P(1) \to P(2)\), \(P(2) \to P(3)\), and so on, one can deduce \(P(n)\) only if \(P(1)\) is independently established. In the present case, \(P(1)\) is false — and from a false \(P(1)\), the chain of implications transmits falsity, not truth, forward through every value of \(n\).

The methodological lesson: an induction proof is incomplete without an explicit base case. Verifying the base case is rarely the hardest part of an induction proof, but it is never optional. A correct inductive step combined with an unverified or false base case proves nothing whatsoever.

Summary

  • Mathematical induction proves a statement “\(P(n)\) holds for every \(n \geq n_0\)” in two parts: a base case (\(P(n_0)\)) and an inductive step (\(P(k) \to P(k+1)\) for every \(k \geq n_0\)).

  • The Principle of Mathematical Induction is an axiom: it cannot be derived from the apparatus of logic alone. It is part of what defines the natural numbers.

  • The inductive hypothesis assumes \(P(k)\) for an arbitrary \(k \geq n_0\); the inductive step then proves \(P(k+1)\).

  • Both the base case and the inductive step are essential. A correct inductive step combined with a missing or false base case proves nothing.

  • Common applications include sum formulas (\(1 + 2 + \cdots + n = n(n+1)/2\); \(1 + 3 + \cdots + (2n-1) = n^2\)) and divisibility results (\(4 \mid 5^n - 1\)).