Ordinary and strong induction
Last modified: 2026-10-27 13:24:37 (PDT)
Source
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Induction” and “More Induction!”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. These come from those notes:
The exercises, the other examples and the text of the false proof are new.
Exercise 1 (Adding unit fractions of neighbors) Consider the claim that for every natural number (Definition: Natural numbers (our convention)) \(n\),
\[ \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n + 1)} = \frac{n}{n + 1}. \]
Solution 1.
For \(n = 1\), the left side is \(\frac{1}{2}\) and the right side is \(\frac{1}{2}\). For \(n = 2\), the left side is \(\frac{1}{2} + \frac{1}{6} = \frac{2}{3}\) and the right side is \(\frac{2}{3}\). For \(n = 3\), the left side is \(\frac{2}{3} + \frac{1}{12} = \frac{3}{4}\) and the right side is \(\frac{3}{4}\).
Suppose \(\frac{1}{1 \cdot 2} + \cdots + \frac{1}{k(k + 1)} = \frac{k}{k + 1}\). Then
\[ \begin{aligned} & \frac{1}{1 \cdot 2} + \cdots + \frac{1}{k(k + 1)} + \frac{1}{(k + 1)(k + 2)} \\&= \frac{k}{k + 1} + \frac{1}{(k + 1)(k + 2)} && \text{(the supposition)} \\&= \frac{k(k + 2) + 1}{(k + 1)(k + 2)} && \text{(common denominator)} \\&= \frac{k^2 + 2k + 1}{(k + 1)(k + 2)} \\&= \frac{(k + 1)^2}{(k + 1)(k + 2)} && \text{(} k^2 + 2k + 1 = (k + 1)^2 \text{)} \\&= \frac{k + 1}{k + 2}, && \text{(cancel } k + 1 \text{)} \end{aligned} \]
which is the claim for \(k + 1\).
Part 1 shows the claim for \(n = 1\), and part 2 carries it from each natural number to the next, so it holds for \(n = 2, 3, 4, \ldots\) in turn.
Definition 1 (Proof by induction) Let \(n_0\) be an integer, and let \(P(n)\) be a predicate about the integers \(n \ge n_0\). A proof by induction (Wikipedia contributors 2026b) on \(n\) shows that \(P(n)\) holds for every integer \(n \ge n_0\) by showing two things:
In the inductive step, the assumption that \(P(n - 1)\) holds is called the induction hypothesis.
Remark 1 (Stepping from \(k\) to \(k + 1\)). Definition 1 states the inductive step as “if \(P(n - 1)\), then \(P(n)\), for every \(n > n_0\)”. Many sources, and part 2 of Solution 1, state it as “if \(P(k)\), then \(P(k + 1)\), for every \(k \ge n_0\)”. The two say the same thing, with \(k = n - 1\), and the rest of this chapter uses the second form.
Writing the goal \(P(k + 1)\) correctly is a common place to go wrong: replace every \(n\) in \(P(n)\) with \(k + 1\), including in the last term of a sum and on the other side of the equation.
Remark 2 (The shape of a proof by induction). A proof by induction that \(P(n)\) holds for every integer \(n \ge n_0\) has two parts:
Base case. Show \(P(n_0)\).
Inductive step. Let \(k \ge n_0\) be an integer, and suppose \(P(k)\).
\(\vdots\)
Therefore \(P(k + 1)\).
So \(P(n)\) holds for every integer \(n \ge n_0\), by induction.
Write out the induction hypothesis \(P(k)\) and the goal \(P(k + 1)\) before starting the step, and mark the line where the step uses the hypothesis.
Example 1 (A sum of products of neighbors) Claim: for every natural number \(n\),
\[ 1 \cdot 2 + 2 \cdot 3 + \cdots + n(n + 1) = \frac{n(n + 1)(n + 2)}{3}. \]
Let \(P(n)\) be this equation, and follow Remark 2 with \(n_0 = 1\).
Base case. For \(n = 1\), the left side is \(1 \cdot 2 = 2\) and the right side is \(\frac{1 \cdot 2 \cdot 3}{3} = 2\).
Inductive step. Let \(k \ge 1\), and suppose \(P(k)\):
\[ 1 \cdot 2 + \cdots + k(k + 1) = \frac{k(k + 1)(k + 2)}{3}. \]
The goal \(P(k + 1)\) is
\[ 1 \cdot 2 + \cdots + k(k + 1) + (k + 1)(k + 2) = \frac{(k + 1)(k + 2)(k + 3)}{3}. \]
Starting from its left side,
\[ \begin{aligned} & 1 \cdot 2 + \cdots + k(k + 1) + (k + 1)(k + 2) \\&= \frac{k(k + 1)(k + 2)}{3} + (k + 1)(k + 2) && \text{(induction hypothesis)} \\&= \frac{k(k + 1)(k + 2) + 3(k + 1)(k + 2)}{3} && \text{(common denominator)} \\&= \frac{(k + 1)(k + 2)(k + 3)}{3}. && \text{(factor out } (k + 1)(k + 2) \text{)} \end{aligned} \]
So \(P(k + 1)\) holds, and by induction \(P(n)\) holds for every natural number \(n\).
Exercise 2 (When does \(2^n\) catch up with \(n^2\)?) Compare \(n^2\) with \(2^n\) for \(n = 1, 2, \ldots, 6\). Find the smallest natural number \(n_0\) such that \(n^2 \le 2^n\) holds for \(n_0\) and for every \(n\) you checked after it.
Solution 2.
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| \(n^2\) | 1 | 4 | 9 | 16 | 25 | 36 |
| \(2^n\) | 2 | 4 | 8 | 16 | 32 | 64 |
The inequality holds for \(n = 1\) and \(n = 2\), fails for \(n = 3\), and holds for \(n = 4, 5, 6\). So \(n_0 = 4\).
Example 2 (An induction that starts at 4) Claim: \(n^2 \le 2^n\) for every integer (Definition: Integers) \(n \ge 4\).
Let \(P(n)\) be the inequality \(n^2 \le 2^n\) (Definition: Inequality), and follow Remark 2 with \(n_0 = 4\). Solution 2 shows that \(n_0 = 1\) would not work, since \(P(3)\) is false.
Base case. \(4^2 = 16 \le 16 = 2^4\).
Inductive step. Let \(k \ge 4\), and suppose \(k^2 \le 2^k\). The goal is \((k + 1)^2 \le 2^{k + 1}\). Since \(k \ge 4\), we have \(k^2 \ge 4k = 2k + 2k \ge 2k + 8 > 2k + 1\). So
\[ \begin{aligned} (k + 1)^2 &= k^2 + 2k + 1 \\&< k^2 + k^2 && \text{(} 2k + 1 < k^2 \text{)} \\&= 2k^2 \\&\le 2 \cdot 2^k && \text{(induction hypothesis)} \\&= 2^{k + 1}. \end{aligned} \]
So \(P(k + 1)\) holds, and by induction \(n^2 \le 2^n\) for every integer \(n \ge 4\). The inductive step works for every \(k \ge 3\), since \(2k + 1 < k^2\) already holds at \(k = 3\). The induction starts at 4 because of the base case: \(P(3)\) is false.
Exercise 3 (Breaking a chocolate bar) A chocolate bar is a row of \(n\) squares. One break splits one piece into two pieces along a line between squares. How many breaks does it take to split a bar of 1, 2, 3 or 4 squares into single squares? Does the answer depend on where you break first?
Solution 3. A bar of 1 square takes 0 breaks, 2 squares take 1, 3 squares take 2, and 4 squares take 3. For 4 squares, breaking first in the middle gives two pieces of 2 squares, which take 1 break each, for \(1 + 1 + 1 = 3\) breaks; breaking first at one end gives pieces of 1 and 3 squares, which take 0 and 2 breaks, for \(1 + 0 + 2 = 3\) breaks. For these bars, the answer does not depend on where you break first.
Definition 2 (Proof by strong induction) Let \(n_0\) be an integer, and let \(P(n)\) be a predicate about the integers \(n \ge n_0\). A proof by strong induction (Wikipedia contributors 2026b) on \(n\) shows that \(P(n)\) holds for every integer \(n \ge n_0\) by showing one thing: for every integer \(n \ge n_0\), if \(P(k)\) holds for every integer \(k\) with \(n_0 \le k < n\), then \(P(n)\) holds.
The assumption that \(P(k)\) holds for every integer \(k\) with \(n_0 \le k < n\) is the strong induction hypothesis.
For \(n = n_0\) no integer \(k\) satisfies \(n_0 \le k < n\), so the strong induction hypothesis is vacuously true, and the proof for \(n = n_0\) is a base case. When the proof for \(n\) needs particular earlier cases that do not exist for the first few \(n\), those few cases are shown separately as further base cases.
Theorem 1 (Breaking a chocolate bar takes one break fewer than its squares) For every natural number (Definition: Natural numbers (our convention)) \(n\), splitting a bar of chocolate, a row of \(n\) squares, into single squares takes exactly \(n - 1\) breaks, however the breaks are made.
Remark 3 (Why the proof needs strong induction). The proof of Theorem 1 uses \(P(a)\) and \(P(b)\), where \(a\) and \(b\) can be any sizes smaller than \(n\), not only \(n - 1\). Ordinary induction gives only \(P(n - 1)\) in the step. Strong induction gives \(P(k)\) for every \(k < n\), which is what the proof needs.
Definition 3 (Recursively defined sequence) Let \(n_0\) be an integer and \(m\) a positive integer. A sequence \(a_{n_0}, a_{n_0 + 1}, \ldots\) is recursively defined (Wikipedia contributors 2026c) by two things:
The initial terms and the recurrence together fix every term: the first \(m\) entries are given, and each later entry follows from the \(m\) entries before it.
Example 3 (Powers of 3) The sequence \(a_0, a_1, \ldots\) with initial term \(a_0 = 1\) and recurrence \(a_n = 3 a_{n-1}\) for \(n \ge 1\) has \(m = 1\), and its terms are \(1, 3, 9, 27, \ldots\) A proof by induction shows \(a_n = 3^n\) for every integer \(n \ge 0\), using the recurrence in the inductive step: if \(a_{n-1} = 3^{n-1}\), then \(a_n = 3 \cdot 3^{n-1} = 3^n\).
Definition 4 (Fibonacci sequence) The Fibonacci sequence \(F_1, F_2, \ldots\) (Wikipedia contributors 2026a) is the recursively defined sequence with \(m = 2\), initial terms \(F_1 = 1\) and \(F_2 = 1\), and recurrence \(F_n = F_{n-1} + F_{n-2}\) for every integer \(n \ge 3\).
Example 4 (The first Fibonacci numbers) \(F_3 = F_2 + F_1 = 1 + 1 = 2\), \(F_4 = F_3 + F_2 = 2 + 1 = 3\), \(F_5 = F_4 + F_3 = 3 + 2 = 5\), and \(F_6 = F_5 + F_4 = 5 + 3 = 8\). So the sequence begins \(1, 1, 2, 3, 5, 8, \ldots\)
Example 5 (Every term of the Fibonacci sequence is less than a power of 2) Let \(F_1, F_2, \ldots\) be the Fibonacci sequence. To prove \(F_n < 2^n\) for every \(n \in \mathbb{N}\), let \(P(n)\) be the inequality \(F_n < 2^n\) and use Definition 2 with \(n_0 = 1\).
Base cases, \(n = 1\) and \(n = 2\). The step below uses the two entries \(F_{n-1}\) and \(F_{n-2}\) before \(F_n\), which do not exist for \(n = 1\) and \(n = 2\), so these two cases are shown directly:
\[ \begin{aligned} F_1 &= 1 < 2 = 2^1 && \text{(} 1 < 2 \text{)} \\ F_2 &= 1 < 4 = 2^2. && \text{(} 1 < 4 \text{)} \end{aligned} \]
Step of the strong induction, \(n \ge 3\). Let \(n \ge 3\), and suppose \(P(k)\) holds for every integer \(k\) with \(1 \le k < n\). Then \(k = n - 1\) and \(k = n - 2\) both satisfy \(1 \le k < n\), so \(F_{n-1} < 2^{n-1}\) and \(F_{n-2} < 2^{n-2}\). Therefore
\[ \begin{aligned} F_n &= F_{n-1} + F_{n-2} && \text{(definition of } F_n \text{, since } n \ge 3 \text{)} \\ &< 2^{n-1} + 2^{n-2} && \text{(strong induction hypothesis, twice)} \\ &< 2^{n-1} + 2^{n-1} && \text{(} 2^{n-2} < 2^{n-1} \text{)} \\ &= 2 \cdot 2^{n-1} && \text{(} a + a = 2a \text{)} \\ &= 2^n, && \text{(} 2 \cdot 2^{n-1} = 2^n \text{)} \end{aligned} \]
which is \(P(n)\). By Definition 2, \(F_n < 2^n\) for every \(n \in \mathbb{N}\).
Example 6 (A proof by induction that fails) Claim (false): in every group of \(n \ge 1\) horses, all the horses are the same color.
“Proof”:
The inductive step fails for \(k = 1\): a group of 2 horses splits into two groups of 1 horse with no horse in both, so nothing links the two colors. So \(P(1)\) does not imply \(P(2)\), and the chain of implications breaks at its first link. An inductive step has to work for every \(k \ge n_0\), including the smallest.