Induction and Recursion
Remark. A proof by induction proves a proposition about every integer from some starting integer on. A sequence defined by a rule on its earlier terms is the usual place to use it. This page defines such sequences, then adds the stronger form, strong induction, that they often need.
1 Recursively defined sequences
Definition 1 (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 [1] by two things:
- Initial terms: specific values for \(a_{n_0}, \ldots, a_{n_0 + m - 1}\).
- Recurrence: a rule that gives \(a_n\) from the \(m\) entries \(a_{n-1}, \ldots, a_{n-m}\) just before it, for every integer \(n \ge n_0 + m\).
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 1 (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 2 (Fibonacci sequence) The Fibonacci sequence \(F_1, F_2, \ldots\) [2] 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\).
2 Strong induction
Definition 3 (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 [3] 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.
Example 3 (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 3 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 3, \(F_n < 2^n\) for every \(n \in \mathbb{N}\).
3 Further reading
- Velleman [4] is a structured introduction to proof techniques, including proof by induction.