Discrete Math › Section E · Sequences › Topic E.4
Exponential sequences and solving recurrences
A recurrence tells you how to step from one term to the next; solving it means finding a closed formula that jumps straight to any term. This topic sums geometric sequences and then solves the recurrences that come up most often, from Fibonacci to divide-and-conquer algorithms.
Why solve a recurrence?
The recurrence \(a_n = 2a_{n-1} + 1\) with \(a_0 = 0\) is easy to state and slow to use: the hundredth term needs a hundred steps. A closed formula, here \(a_n = 2^n - 1\), gives any term at once and shows the growth rate at a glance. The topic "Polynomial sequences" handled recurrences that add a polynomial at each step. This topic deals with recurrences that multiply, whose solutions involve powers \(r^n\). The tools are a sum formula for geometric sequences, unrolling, the characteristic root technique, and a trick for an added constant.
Summing a geometric sequence
Let \(S = a + ar + ar^2 + \cdots + ar^n\), a sum of \(n + 1\) terms. Multiply by \(r\) to shift every term one place along: \(rS = ar + ar^2 + \cdots + ar^{n+1}\). Subtract the first line from the second, and all the middle terms cancel, leaving \(rS - S = ar^{n+1} - a\). So, for \(r \ne 1\),
This multiply, shift and subtract method is the same one used in the algebra topic "Geometric sequences and series", which counted \(n\) terms from \(a_1\) and so wrote \(r^n\) where this formula has \(r^{n+1}\).
Worked example: a geometric sum
Find \(3 + 6 + 12 + \cdots + 3 \cdot 2^9\). 1. The first term is \(a = 3\), the ratio is \(r = 2\), and the exponents run from 0 to 9, so there are 10 terms. 2. Apply the formula:
3. Check on a small case: \(3 + 6 + 12 = 21\), and the formula with top exponent 2 gives \(3(2^3 - 1) = 21\). The same formula shows that \(1 + 2 + 4 + \cdots + 2^{n-1} = 2^n - 1\): one less than the next power of 2.
Unrolling a recurrence
To unroll, substitute the recurrence into itself until a pattern appears. For \(a_n = 2a_{n-1} + 1\) with \(a_0 = 0\):
Continuing \(n\) times gives \(2^n a_0 + 2^{n-1} + \cdots + 2 + 1\), and since \(a_0 = 0\) this is the geometric sum \(2^n - 1\). This is the move count for the Towers of Hanoi, met again in "Recursion and structural induction". Unrolling produces a strong guess; a proof by induction, the method of the topic "Proof by induction", makes it certain.
The characteristic root technique
For a second-order linear homogeneous recurrence \(a_n = c_1 a_{n-1} + c_2 a_{n-2}\), try a solution of the form \(a_n = r^n\). Dividing \(r^n = c_1 r^{n-1} + c_2 r^{n-2}\) by \(r^{n-2}\) gives the characteristic equation
If it has two distinct roots \(r_1\) and \(r_2\), every solution has the form \(a_n = \alpha r_1^n + \beta r_2^n\). This works because a sum of constant multiples of solutions is again a solution. The two initial conditions then fix \(\alpha\) and \(\beta\).
Worked example: two distinct roots
Solve \(a_n = a_{n-1} + 6a_{n-2}\) with \(a_0 = 1\) and \(a_1 = 8\). 1. Characteristic equation: \(r^2 - r - 6 = 0\), which factors as \((r - 3)(r + 2) = 0\). Roots 3 and \(-2\). 2. General solution: \(a_n = \alpha 3^n + \beta(-2)^n\). 3. Initial conditions: \(\alpha + \beta = 1\) and \(3\alpha - 2\beta = 8\). Substituting \(\beta = 1 - \alpha\) gives \(5\alpha = 10\), so \(\alpha = 2\) and \(\beta = -1\). 4. So \(a_n = 2 \cdot 3^n - (-2)^n\). Check: the recurrence gives \(a_2 = 8 + 6 = 14\) and \(a_3 = 14 + 48 = 62\); the formula gives \(18 - 4 = 14\) and \(54 + 8 = 62\).
The Fibonacci numbers in closed form
For \(F_n = F_{n-1} + F_{n-2}\) the characteristic equation is \(r^2 - r - 1 = 0\), with roots \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\), the golden ratio, and \(\psi = \frac{1 - \sqrt{5}}{2} \approx -0.618\). Fitting \(F_0 = 0\) and \(F_1 = 1\) gives Binet's formula:
Every \(\sqrt{5}\) cancels and the result is always a whole number. Because \(|\psi| < 1\), the \(\psi^n\) term shrinks to nothing, so \(F_n\) grows like \(\varphi^n\) and the ratio \(F_{n+1}/F_n\) approaches \(\varphi\).
Worked example: a repeated root
Solve \(a_n = 6a_{n-1} - 9a_{n-2}\) with \(a_0 = 2\) and \(a_1 = 9\). 1. Characteristic equation: \(r^2 - 6r + 9 = (r - 3)^2 = 0\). The root 3 is repeated. 2. With a repeated root \(r\), the general solution is \(a_n = (\alpha + \beta n) r^n\); the extra factor \(n\) supplies the second independent solution. 3. From \(a_0 = 2\): \(\alpha = 2\). From \(a_1 = 9\): \((2 + \beta) \cdot 3 = 9\), so \(\beta = 1\). 4. So \(a_n = (n + 2)3^n\). Check: the recurrence gives \(a_2 = 54 - 18 = 36\), and the formula gives \(4 \cdot 9 = 36\).
Recurrences with an added constant
For \(a_n = c\,a_{n-1} + k\) with \(c \ne 1\), first find a constant solution \(p\) by solving \(p = cp + k\). Every solution is that constant plus a solution of the plain recurrence \(a_n = c\,a_{n-1}\): \(a_n = \alpha c^n + p\). Example: \(a_n = 3a_{n-1} + 2\) with \(a_0 = 4\). Solving \(p = 3p + 2\) gives \(p = -1\), so \(a_n = \alpha 3^n - 1\), and \(a_0 = 4\) forces \(\alpha = 5\). Thus \(a_n = 5 \cdot 3^n - 1\), giving 4, 14, 44, as the recurrence does. Fit \(\alpha\) only after adding \(p\).
Divide-and-conquer recurrences
Algorithms that split a problem in half give recurrences in \(n/2\). Merge sort sorts two halves and merges them in about \(n\) steps: \(T(n) = 2T(n/2) + n\). For \(n = 2^m\) and \(T(1) = 0\), unrolling \(m\) times gives \(m\) levels that each cost \(n\), so \(T(n) = n \log_2 n\); check \(T(8) = 24 = 8 \times 3\). Binary search halves the list with one comparison: \(T(n) = T(n/2) + 1\) with \(T(1) = 1\) gives \(\log_2 n + 1\). The master theorem, met in algorithms courses, packages the general case \(T(n) = aT(n/b) + f(n)\).
Common mistakes to avoid
First, miscounting the terms of a geometric sum: exponents 0 to \(n\) make \(n + 1\) terms. Second, sign slips in the characteristic equation: \(a_n = 5a_{n-1} - 6a_{n-2}\) gives \(r^2 - 5r + 6 = 0\), not \(r^2 - 5r - 6 = 0\). Third, using \(\alpha r^n + \beta r^n\) for a repeated root, which leaves only one free constant; use \((\alpha + \beta n)r^n\). Fourth, fitting the constants before adding the particular solution. Fifth, never checking the formula against terms computed from the recurrence.
Key takeaways
A geometric sum is \(\frac{a(r^{n+1} - 1)}{r - 1}\), found by multiplying, shifting and subtracting. Unrolling turns simple recurrences into sums. For \(a_n = c_1 a_{n-1} + c_2 a_{n-2}\), solve \(r^2 - c_1 r - c_2 = 0\): distinct roots give \(\alpha r_1^n + \beta r_2^n\), a repeated root gives \((\alpha + \beta n)r^n\), and the initial conditions fix the constants. An added constant contributes a constant particular solution. Fibonacci grows like \(\varphi^n\), and halving recurrences lead to logarithms.
Flashcards
Flashcard
a(rⁿ⁺¹ − 1)/(r − 1), for r ≠ 1
Test your understanding
Question 1 of 5
What is 2 + 6 + 18 + … + 2 · 3⁵?
Question 2 of 5
What is the general solution of aₙ = 5aₙ₋₁ − 6aₙ₋₂?
Question 3 of 5
Solve aₙ = 4aₙ₋₁ − 4aₙ₋₂ with a₀ = 1 and a₁ = 6.
Question 4 of 5
Solve aₙ = 3aₙ₋₁ − 4 with a₀ = 5.
Question 5 of 5
As n grows, what does the ratio Fₙ₊₁/Fₙ of consecutive Fibonacci numbers approach?
