In the previous article, the Principle of Mathematical Induction (PMI) assumed only \(P(k)\) to prove \(P(k+1)\). That is enough in many cases. But what if step \(k+1\) depends not only on \(k\), but on two or more earlier cases at the same time?
The answer is Strong Induction, a variant that assumes the truth of all earlier cases at once.
Why Strong Induction? #
Simple induction is enough when each step depends only on the immediately preceding case. Strong induction is needed when the reasoning has to reach back more than one level, which happens often in computer science:
- Multi-step recurrent sequences: Fibonacci uses \(F_{k+1} = F_k + F_{k-1}\); proving any property of this kind of sequence by induction requires both earlier cases.
- Divide-and-conquer algorithms: merge sort and quick sort split the problem into parts of arbitrary size (not necessarily \(k-1\)); the correctness proof needs the hypothesis for all smaller subproblems.
- Factorization and number theory: the proof that every integer \(n > 1\) has a prime factor requires the hypothesis for any divisor of \(n\), which can be much smaller than \(n-1\).
- Structural properties of trees: proofs about a tree with \(n\) nodes often fall back on subtrees of any size smaller than \(n\).
This article presents the technique with examples of increasing complexity, culminating in Binet’s Formula for Fibonacci.
The Fibonacci Sequence #
Before the formal principle, it is worth introducing the sequence that will be used as an example throughout this article.
First terms: \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\)
Each term is the sum of the two before it:
$$F_3 = F_2 + F_1 = 2, \quad F_4 = F_3 + F_2 = 3, \quad F_5 = F_4 + F_3 = 5, \ldots$$An observed identity #
Computing the first cases:
| \(n\) | \(F_1^2 + \cdots + F_n^2\) | \(F_n \cdot F_{n+1}\) |
|---|---|---|
| 1 | 1 | \(1 \cdot 1 = 1\) |
| 2 | 2 | \(1 \cdot 2 = 2\) |
| 3 | 6 | \(2 \cdot 3 = 6\) |
| 4 | 15 | \(3 \cdot 5 = 15\) |
The pattern suggests: \(F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}\).
This identity can be proved by simple induction (each step only needs the previous case):
Base (\(n = 1\)): \(F_1^2 = 1 = F_1 \cdot F_2\) ✓
IH: \(F_1^2 + \cdots + F_k^2 = F_k \cdot F_{k+1}\)
Inductive step (\(n = k+1\)):
$$F_1^2 + \cdots + F_k^2 + F_{k+1}^2 \stackrel{\text{IH}}{=} F_k F_{k+1} + F_{k+1}^2 = F_{k+1}(F_k + F_{k+1}) = F_{k+1} \cdot F_{k+2}$$Therefore, \(F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}\), which is what we wanted to prove. \(\blacksquare\)
Application: recursive Fibonacci and exponential complexity
The naive recursive implementation of Fibonacci in Python directly mirrors the definition:
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)Each call generates two smaller calls (fib(n-1) and fib(n-2)), and many
subproblems are recomputed over and over. Letting \(C_n\) be the number of
calls made by fib(n), we have \(C_1 = C_2 = 1\) and
\(C_n = 1 + C_{n-1} + C_{n-2}\), and a strong induction shows that \(C_n = 2F_n - 1\).
The cost therefore grows like \(F_n\) itself, and \(F_n\) grows
exponentially: by Binet’s Formula, proved in Exercise 4,
\(F_n \approx \varphi^n/\sqrt{5}\), with \(\varphi \approx 1.618\). For
\(n = 50\), that is more than 25 billion calls. Example 1, below, gives the
other side of the calculation: the upper bound \(F_n < \left(\frac{7}{4}\right)^n\)
guarantees that the growth is no worse than exponential.
The solution is memoization, which stores each computed \(F_k\) and reuses it:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 2:
return 1
return fib(n - 1) + fib(n - 2)With memoization, each value is computed only once, with complexity \(O(n)\).
The impact shows up in practical measurements. For \(n = 35\), with Python 3.13 on a recent personal computer:
| Version | Time (1 run) | Complexity |
|---|---|---|
| Naive | ~0.75 s | exponential |
| Memoized | ~0.01 ms | \(O(n)\) |
| Binet | ~0.01 ms | \(O(1)\) |
The exact times vary from machine to machine; what repeats is the ratio. Each extra unit in \(n\) multiplies the time of the naive version by about \(\varphi \approx 1.6\): from \(n = 30\) to \(n = 35\), the time becomes about ten times larger.
Binet’s Formula, which will be proved below in Exercise 4, reduces the computation to \(O(1)\) arithmetic operations, and strong induction is the mathematical guarantee that the formula is correct for every \(n\). But the guarantee is mathematical: the computer does not work with an exact \(\sqrt{5}\). In 64-bit floating point, the formula is correct up to \(F_{70}\) and fails from \(F_{71}\) on:
from math import sqrt
phi = (1 + sqrt(5)) / 2
psi = (1 - sqrt(5)) / 2
def fib_binet(n):
return round((phi**n - psi**n) / sqrt(5))
def fib_exact(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib_binet(70) == fib_exact(70)) # True
print(fib_binet(71)) # 308061521170130
print(fib_exact(71)) # 308061521170129The float64 keeps about 16 significant digits, and \(F_{71}\) already has
15: the small rounding error in \(\sqrt{5}\) and in \(\varphi^n\) now
reaches the units digit. The
article on the IEEE 754 standard
explains where this limit comes from. For exact values with large \(n\),
the versions that use only integers (memoized or iterative) are the right
choice.
The redundancy of the computation is evident in the call tree of fib(5):
fib(3) is computed twice and fib(2) three times, and the problem worsens
exponentially with \(n\).
flowchart TD F5["fib(5)"] --> F4["fib(4)"] F5 --> F3a["fib(3)"] F4 --> F3b["fib(3)"] F4 --> F2a["fib(2)"] F3a --> F2b["fib(2)"] F3a --> F1a["fib(1)"] F3b --> F2c["fib(2)"] F3b --> F1b["fib(1)"]
Principle of Strong Induction #
Let \(P(n)\) be a property of \(n \in \mathbb{N}\). If:
- Base: \(P(1)\) is true
- Step: \(\bigl[P(1), P(2), \ldots, P(k)\ \text{are all true}\bigr] \Rightarrow P(k+1)\)
Then \(P(n)\) is true for every \(n \in \mathbb{N}\).
The Principle of Strong Induction is equivalent to the standard PMI: any proposition that can be proved by one can also be proved by the other. The difference is practical: the stronger hypothesis of strong induction makes certain proofs much more direct.
The difference lies in the hypothesis: in the PMI, we assume only \(P(k)\). In strong induction, also called complete induction, we assume \(P(1), P(2), \ldots, P(k)\), all earlier cases simultaneously. This is particularly useful when \(P(k+1)\) depends on more distant cases (such as \(P(k-1)\), \(P(k-2)\), etc.).
The diagram below contrasts the two chains of implication: in simple induction, each node receives an arrow only from the previous one; in strong induction, each node receives arrows from all the previous ones.
flowchart LR
subgraph simples["Simple Induction"]
direction LR
P1["P(1)"] --> P2["P(2)"]
P2 --> P3["P(3)"]
P3 --> P4["P(4)"]
P4 --> PN["..."]
end
subgraph forte["Strong Induction"]
direction LR
Q1["P(1)"] --> Q3["P(3)"]
Q2["P(2)"] --> Q3
Q1 --> Q4["P(4)"]
Q2 --> Q4
Q3 --> Q4
Q4 --> QN["..."]
end
Structure of the proof #
Every proof by strong induction follows the same three-step structure:
| Step | What to do |
|---|---|
| Base | Verify \(P(1)\) (and sometimes \(P(2)\) or more) |
| Strong hypothesis (SIH) | Assume \(P(1), P(2), \ldots, P(k)\) are true for an arbitrarily fixed \(k \geq 1\) |
| Inductive step | Prove \(P(k+1)\) using the SIH |
When the recurrence in the inductive step reaches back \(r\) positions (that is, \(P(k+1)\) depends on \(P(k), P(k-1), \ldots, P(k-r+1)\)), you must verify \(r\) base cases independently. For Fibonacci (\(r = 2\)), the cases \(P(1)\) and \(P(2)\) are needed; for a recurrence of order 3, they would be \(P(1)\), \(P(2)\) and \(P(3)\). Without these initial cases, the inductive chain does not have a sufficient starting point.
There is a leaner formulation of strong induction: if, for every \(n \geq 1\), the truth of \(P(m)\) for all \(m < n\) implies \(P(n)\), then \(P(n)\) holds for every \(n\). It seems to dispense with the base, but it does not: for \(n = 1\) there is no \(m < 1\), the hypothesis is empty, and the implication requires proving \(P(1)\) with no help at all, which is precisely the base case. The version with an explicit base, used in this article, just keeps that step in plain view.
Application: Merge sort and correctness by divide and conquer
Merge sort sorts a list by splitting it in half, sorting each half recursively and merging the results:
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
return result + a[i:] + b[j:]
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)The correctness proof follows exactly the structure of strong induction:
| Step | In merge sort |
|---|---|
| Base | len(lst) <= 1: an empty or one-element list is already sorted |
| SIH | merge_sort(lst[:mid]) and merge_sort(lst[mid:]) return sorted lists (subproblems of sizes \(\lfloor n/2 \rfloor\) and \(\lceil n/2 \rceil\), both \(\leq k\)) |
| Step | merge(left, right): merging two sorted lists produces a sorted list |
Simple hypothesis would not be enough here: the subproblems have sizes \(\lfloor n/2 \rfloor\) and \(\lceil n/2 \rceil\), not necessarily \(n-1\). The SIH guarantees correctness for any subproblem size smaller than \(n\).
As for the cost, merge sort satisfies \(T(n) = 2T(n/2) + n\), solved, with the answer \(O(n \log n)\), in the section on divide and conquer of the article on recurrence relations.
The call tree of merge_sort([5, 3, 8, 1]) contrasts with the Fibonacci one:
each subproblem is computed only once and the results are combined from the
bottom up by the merges.
flowchart TD A["[5, 3, 8, 1]"] -->|split| B["[5, 3]"] A -->|split| C["[8, 1]"] B -->|split| D["[5]"] B -->|split| E["[3]"] C -->|split| F["[8]"] C -->|split| G["[1]"] D & E -->|merge| H["[3, 5]"] F & G -->|merge| I["[1, 8]"] H & I -->|merge| J["[1, 3, 5, 8] ✓"]
Example 1: \(F_n < \left(\frac{7}{4}\right)^n\) #
This result does not follow directly from simple induction: \(F_{k+1} = F_k + F_{k-1}\) depends on two earlier cases, and the simple IH delivers only one. Since the two inductions are equivalent, there are ways around it (proving, for example, \(P(k)\) and \(P(k+1)\) together), but strong induction makes the proof direct.
Base: \(P(1)\): \(F_1 = 1 < \dfrac{7}{4}\) ✓
\(P(2)\): \(F_2 = 1 < \left(\dfrac{7}{4}\right)^2 = \dfrac{49}{16}\) ✓
SIH: \(F_j < \left(\dfrac{7}{4}\right)^j\) for \(j = 1, 2, \ldots, k\).
Inductive step (\(n = k+1\), with \(k \geq 2\)):
$$F_{k+1} = F_k + F_{k-1} \stackrel{\text{SIH}}{<} \left(\frac{7}{4}\right)^k + \left(\frac{7}{4}\right)^{k-1} = \left(\frac{7}{4}\right)^{k-1}\left(\frac{7}{4} + 1\right) = \left(\frac{7}{4}\right)^{k-1} \cdot \frac{11}{4}$$Since \(\dfrac{11}{4} < \left(\dfrac{7}{4}\right)^2 = \dfrac{49}{16}\):
$$F_{k+1} < \left(\frac{7}{4}\right)^{k-1} \cdot \left(\frac{7}{4}\right)^2 = \left(\frac{7}{4}\right)^{k+1}$$Therefore, \(F_n < \left(\dfrac{7}{4}\right)^n\), which is what we wanted to prove. \(\blacksquare\)
Generalized Strong Induction (base at \(n_0\)) #
Just as the PMI has a generalized version, so does strong induction:
To prove \(P(n)\) for every \(n \geq n_0\):
- Base: verify \(P(n_0)\)
- Hypothesis: \(P(n_0), P(n_0+1), \ldots, P(k)\) are true
- Step: prove \(P(k+1)\)
Example 2: Prime Factorization #
Example 2 applies the generalized variant with \(n_0 = 2\): the statement holds for every \(n > 1\), and there are no integers greater than 1 and smaller than 2 to check before the base case.
Every integer \(n > 1\) is prime or can be written as a product of prime numbers.
Base (\(n = 2\)): \(2\) is prime ✓
SIH: \(P(2), P(3), \ldots, P(k)\) are true.
Step (\(n = k+1\)):
- If \(k+1\) is prime, \(P(k+1)\) is true.
- If \(k+1\) is not prime, then \(k+1 = a \cdot b\) with \(2 \leq a, b < k+1\).
- By the SIH, \(a\) and \(b\) are prime or products of primes.
- Hence \(k+1 = a \cdot b\) is also a product of primes.
Therefore, every integer \(n > 1\) is prime or a product of primes, which is what we wanted to prove. \(\blacksquare\)
Why is strong induction the natural tool here? Because when \(k+1\) decomposes as \(a \cdot b\), there is no guarantee that \(a\) or \(b\) is equal to \(k\). It can be any value between 2 and \(k-1\). The simple hypothesis, which delivers only \(P(k)\), does not support this argument.
Example 3: The Chocolate Bar #
A chocolate bar of \(m \times n\) squares can be broken into individual squares in many different orders. How many breaks are needed in total?
Let \(Q(k)\): “breaking a piece of \(k\) squares into units requires exactly \(k-1\) breaks.” We prove \(Q(k)\) by strong induction on \(k\).
Base (\(k=1\)): a single square is already broken apart; \(0 = 1-1\) breaks. ✓
SIH: \(Q(j)\) is true for every \(j = 1, 2, \ldots, k\).
Inductive step (\(k+1\) squares):
The first break splits the piece into two parts of sizes \(a\) and \(b\), with \(a + b = k+1\) and \(1 \leq a, b \leq k\). By the SIH, the part with \(a\) squares needs \(a-1\) breaks and the one with \(b\) needs \(b-1\). The total is:
$$1 + (a-1) + (b-1) = a + b - 1 = (k+1) - 1$$Therefore, a piece of \(k\) squares requires exactly \(k - 1\) breaks for every \(k \geq 1\), which is what we wanted to prove. \(\blacksquare\)
In particular, an \(m \times n\) bar, with \(mn\) squares, needs exactly \(mn - 1\) breaks, whatever the order.
Strong induction is the natural tool here: when breaking \(k+1\) squares, the sizes \(a\) and \(b\) can be any values between 1 and \(k\), not necessarily \(k\). The SIH guarantees correctness for all these cases at once.
Comparison: Simple Induction vs. Strong Induction #
| Feature | Simple Induction | Strong Induction |
|---|---|---|
| Hypothesis | \(P(k)\) is true | \(P(1), \ldots, P(k)\) are true |
| Step | \(P(k) \Rightarrow P(k+1)\) | \(P(1) \wedge \cdots \wedge P(k) \Rightarrow P(k+1)\) |
| When to use | Next step depends only on \(k\) | Next step depends on multiple cases |
| Equivalence | Yes, they are equivalent | Yes, they are equivalent |
Exercises #
Practice by applying the structure of strong induction. Exercises 1 and 2 are of intermediate difficulty; exercises 3 and 4 require more algebraic work; exercise 5 is a fundamental result in computer science.
Exercise 1: Bound for Fibonacci
Prove by strong induction that \(F_n \leq 2^{n-1}\) for every \(n \geq 1\).
Proof
Base (\(n=1\)): \(F_1 = 1 = 2^0\) ✓
Base (\(n=2\)): \(F_2 = 1 \leq 2^1 = 2\) ✓
SIH: \(F_j \leq 2^{j-1}\) for every \(j = 1, 2, \ldots, k\) with \(k \geq 2\).
Inductive step (\(n = k+1\)):
$$F_{k+1} = F_k + F_{k-1} \stackrel{\text{SIH}}{\leq} 2^{k-1} + 2^{k-2} = 3 \cdot 2^{k-2} \leq 4 \cdot 2^{k-2} = 2^k$$Therefore, \(F_n \leq 2^{n-1}\), which is what we wanted to prove. \(\blacksquare\)
Exercise 2: Postage stamps
Prove by strong induction that any amount \(n \geq 8\) cents can be paid exactly using 3-cent and 5-cent stamps.
Proof
Base (\(n=8\)): \(8 = 3 + 5\) ✓
Base (\(n=9\)): \(9 = 3 + 3 + 3\) ✓
Base (\(n=10\)): \(10 = 5 + 5\) ✓
SIH: every amount \(j\) with \(8 \leq j \leq k\) can be paid, for some \(k \geq 10\).
Inductive step (\(n = k+1 \geq 11\)):
Since \(k+1 \geq 11\), we have \((k+1) - 3 = k-2 \geq 8\). By the SIH, \(k-2\) cents can be paid with 3-cent and 5-cent stamps. Adding one 3-cent stamp, we get \((k-2)+3 = k+1\) cents.
Therefore, every amount \(n \geq 8\) cents can be paid, which is what we wanted to prove. \(\blacksquare\)
The statement starts at 8 because 7 is the largest amount that cannot be paid with 3-cent and 5-cent stamps, and this is no accident. Given two coprime positive integers \(a\) and \(b\), the largest value that cannot be written as a sum of terms \(a\) and \(b\) is \(ab - a - b\); for \(a = 3\) and \(b = 5\): \(15 - 3 - 5 = 7\). The formula already appears in a work by James Joseph Sylvester from 1882, and the general question, with any number of values, is known as the Frobenius problem, in honor of Ferdinand Frobenius. For three or more values, no explicit formula is known. For the computational complexity of a variant of the problem, see this article.
Exercise 3: Sequence with two base cases
Let \(\{a_n\}\) be defined by \(a_1 = 1\), \(a_2 = 5\) and \(a_n = a_{n-1} + 2a_{n-2}\) for \(n \geq 3\). Show by strong induction that \(a_n = 2^n + (-1)^n\) for every \(n \geq 1\).
Proof
Base (\(n=1\)): \(2^1 + (-1)^1 = 1 = a_1\) ✓
Base (\(n=2\)): \(2^2 + (-1)^2 = 5 = a_2\) ✓
SIH: \(a_i = 2^i + (-1)^i\) for every \(i = 1, 2, \ldots, k\) with \(k \geq 2\).
Inductive step (\(n = k+1\)):
$$a_{k+1} = a_k + 2a_{k-1} \stackrel{\text{SIH}}{=} \bigl[2^k + (-1)^k\bigr] + 2\bigl[2^{k-1} + (-1)^{k-1}\bigr]$$$$= 2^k + (-1)^k + 2^k + 2(-1)^{k-1} = 2^{k+1} + (-1)^{k-1}\bigl[(-1) + 2\bigr] = 2^{k+1} + (-1)^{k+1}$$
Therefore, \(a_n = 2^n + (-1)^n\), which is what we wanted to prove. \(\blacksquare\)
The expression in Exercise 4 is named after Jacques Binet, who published it in 1843, but it was already in use in the 18th century by Abraham de Moivre, by members of the Bernoulli family and by Leonhard Euler, more than a century earlier (see the section on the formula in the Fibonacci sequence article and the history of the golden ratio). It is a classic case of Stigler’s Law: “no scientific discovery is named after its original discoverer.”
Exercise 4: Binet’s Formula for Fibonacci
Binet’s Formula gives the \(n\)-th Fibonacci term directly:
$$F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$$Prove this formula by strong induction.
Proof
Let \(\varphi = \dfrac{1+\sqrt{5}}{2}\) and \(\psi = \dfrac{1-\sqrt{5}}{2}\) (\(\varphi\) is the golden ratio).
Base (\(n=1\)): \(\dfrac{1}{\sqrt{5}}(\varphi - \psi) = \dfrac{1}{\sqrt{5}} \cdot \sqrt{5} = 1 = F_1\) ✓
Base (\(n=2\)): \(\dfrac{1}{\sqrt{5}}(\varphi^2 - \psi^2) = \dfrac{1}{\sqrt{5}}(\varphi+\psi)(\varphi-\psi) = \dfrac{1}{\sqrt{5}} \cdot 1 \cdot \sqrt{5} = 1 = F_2\) ✓
SIH: \(F_i = \dfrac{\varphi^i - \psi^i}{\sqrt{5}}\) for every \(i = 1, 2, \ldots, k\) with \(k \geq 2\).
Inductive step (\(n = k+1\)):
$$F_{k+1} = F_k + F_{k-1} \stackrel{\text{SIH}}{=} \frac{\varphi^k - \psi^k}{\sqrt{5}} + \frac{\varphi^{k-1} - \psi^{k-1}}{\sqrt{5}} = \frac{\varphi^{k-1}(\varphi+1) - \psi^{k-1}(\psi+1)}{\sqrt{5}}$$Since \(\varphi^2 = \varphi + 1\) and \(\psi^2 = \psi + 1\) (a property of the golden ratio):
$$F_{k+1} = \frac{\varphi^{k-1} \cdot \varphi^2 - \psi^{k-1} \cdot \psi^2}{\sqrt{5}} = \frac{\varphi^{k+1} - \psi^{k+1}}{\sqrt{5}}$$Therefore, \(F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}\), which is what we wanted to prove. \(\blacksquare\)
The formula also explains why \(\varphi\) appears: since \(|\psi| < 1\), the term \(\psi^n\) shrinks until it vanishes, and the ratio of two consecutive terms, \(F_{n+1}/F_n\), approaches \(\varphi\). The figure below shows this approximation in the form of rectangles: squares with Fibonacci sides, fitted side by side, form rectangles ever closer to the golden proportion.
Exercise 5: Binary representation
Prove by strong induction that every integer \(n \geq 1\) can be written as a sum of distinct powers of 2 (binary representation).
Proof
Base (\(n=1\)): \(1 = 2^0\). ✓
SIH: every integer \(j\) with \(1 \leq j \leq k\) has a binary representation.
Inductive step (\(n = k+1\)):
- If \(k+1\) is odd: then \(k\) is even. By the SIH, \(k\) has a binary representation using only the powers \(2^1, 2^2, \ldots\) (since \(k\) is even, it does not contain \(2^0\)). Adding \(2^0\) we obtain a representation of \(k+1\) with distinct powers. ✓
- If \(k+1\) is even: then \(\dfrac{k+1}{2} \leq k\). By the SIH, \(\dfrac{k+1}{2}\) has a binary representation \(2^{a_1} + \cdots + 2^{a_r}\). Adding 1 to each exponent (equivalent to multiplying by 2) we obtain \(k+1 = 2^{a_1+1} + \cdots + 2^{a_r+1}\), with distinct powers. ✓
Therefore, every integer \(n \geq 1\) can be written as a sum of distinct powers of 2, which is what we wanted to prove. \(\blacksquare\)
Summary Table #
The results proved in this article, gathered for quick reference:
| Result | Statement |
|---|---|
| Fibonacci identity | \(F_1^2 + F_2^2 + \cdots + F_n^2 = F_n \cdot F_{n+1}\) |
| Exponential bound | \(F_n < \left(\dfrac{7}{4}\right)^n\) |
| Prime factorization | Every \(n > 1\) is prime or a product of primes |
| Chocolate bar (Example 3) | An \(m \times n\) bar requires exactly \(mn - 1\) breaks |
| Bound for Fibonacci (Ex. 1) | \(F_n \leq 2^{n-1}\) |
| Postage stamps (Ex. 2) | Every \(n \geq 8\) cents can be paid with 3-cent and 5-cent stamps |
| Recurrent sequence (Ex. 3) | \(a_n = 2^n + (-1)^n\) where \(a_n = a_{n-1} + 2a_{n-2}\) |
| Binet’s Formula (Ex. 4) | \(F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}\) with \(\varphi = \dfrac{1+\sqrt{5}}{2}\) |
| Binary representation (Ex. 5) | Every integer \(n \geq 1\) has a base-2 representation |
Next Steps #
The Fibonacci recurrence is an example of a recurrence relation, a formula that defines each term from earlier terms. The next article generalizes this idea, presenting systematic techniques for solving this kind of equation.
See you then!
