📋 Changes in this PR: State Machines and Finite Automata, Calendar, Contrapositive and Contradiction, Inference and Direct Proof, Logical Equivalence and Negation, Functional Programming, Graphs, Proving Non-Conditional Statements, Mathematical Induction, Loop Invariants, Predicates and Quantifiers, Propositional Logic, Recurrence Relations and Growth Rates, Recursion, Relations, Proofs with Sets, Sets, WWU CSCI 201 Syllabus, Trees, Expressions and Algorithms, Functions, Growth Rates, Math for Computer Science, Induction and Recursion, Notation, Number Systems, Proof Writing, Relations, Sets
💡 Tip: If change highlighting is glitchy, add the no-preview-highlights label to this PR to disable it.
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 (Wikipedia contributors 2026c) 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\).
Example 2 (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\)
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 (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.
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}\).
Back to top