Lecture 16 — Solving Recurrence Relations
Pre-work: Video 020 (Solving Recurrence Relations). See solving-recurrence-relations for the reference material — arithmetic and geometric sequences, the two proof methods and the Tower of Hanoi — and recursive-definitions for the definitions this lecture starts from.
Learning goals
- Become more familiar with recursive definitions of sequences.
- Gain fluency in moving between a recursive definition and an explicit formula.
Why the second goal is worth having
Put the two forms side by side and ask for the same thing from each, say the term at \(n = 1000\):
| Form | Example | Getting \(a_{1000}\) |
|---|---|---|
| Explicit formula | \(a_n = 7n^2\) for all \(n \in \mathbb{Z}^{+}\) | substitute: \(7(1000)^2\) — one step |
| Recursive definition | \(a_0 = 4\) and \(a_n = 5a_{n-1} + 3\) | compute \(a_1, a_2, \dots\) all the way up — a thousand steps |
That gap is the motivation for the whole topic. A recursive definition is often the easy thing to write down (it is how the Tower of Hanoi and the Fibonacci numbers naturally arise), and an explicit formula is the thing you want to compute with. The topic is converting the first into the second.
Calculating terms gives a guess, not a proof
To show that a recursive definition is the same as an explicit formula, it is not enough to calculate values and show they give the same terms. Calculating terms produces a guess, never a proof. Any finite run of terms is consistent with infinitely many formulas (see sequences-and-summations), so agreement on the first five terms says nothing about the sixth. Terms are calculated to have something to prove. In the two methods below, “write out the first few terms and guess” is a separate step from “prove that your guess is correct”.
Question 3 of the pre-class work asks whether such a claim is true or false. It is worked below, twice, once by each method.
Arithmetic and geometric sequences
For a sequence \(a_0, a_1, a_2, \dots\):
| Recurrence relation | Explicit formula | |
|---|---|---|
| Arithmetic | \(a_k = a_{k-1} + d\) for integers \(k \geq 1\) | \(a_n = a_0 + dn\) for integers \(n \geq 0\) |
| Geometric | \(a_k = r \cdot a_{k-1}\) for integers \(k \geq 1\) | \(a_n = a_0 \cdot r^{\,n}\) for integers \(n \geq 0\) |
The four formulas look alike. The two written in \(k\) with \(a_{k-1}\) on the right are the recurrence relations; the two written in \(n\) are the explicit formulas.
For example, \(2, 6, 18, 54, \dots\) multiplies by \(3\) each step, so \(r = 3\), and with \(a_0 = 2\) the explicit formula is \(a_n = 2 \cdot 3^{\,n}\).
Worked: geometric but not arithmetic
The three terms \(\tfrac{5}{8}, \tfrac{5}{2}, 10\) could be three consecutive terms of what type of sequence?
A geometric sequence. Putting them over a common denominator, \(\tfrac{5}{8}, \tfrac{20}{8}, \tfrac{80}{8}\), makes both tests quick. Run both on the same three terms, with the differences above the row and the ratios below it:
Figure 1: Both tests, run on the same three terms. Rewriting over the common denominator \(8\) makes each test one subtraction or one division. The differences \(\tfrac{15}{8}\) and \(\tfrac{60}{8}\) disagree, so the terms are not arithmetic; the ratios are both \(4\), so they are geometric with \(r = 4\). Neither verdict is evidence about the other, which is what the answer both gets wrong.
The answer “both” is the trap. Passing the ratio test earns nothing on the difference test. The two conditions are independent.
Worked: both arithmetic and geometric
The three terms \(2, 2, 2\) could be three consecutive terms of what type of sequence?
Both. The differences are all \(0\) (arithmetic, \(d = 0\)) and the ratios are all \(1\) (geometric, \(r = 1\)).
This is a constant sequence, \(a_n = c\) for all \(n \in \mathbb{Z}^{+}\). The constant sequences are not just examples of the overlap but the whole of it — \(a_n = a_0 + dn\) and \(a_n = a_0 r^{\,n}\) can agree for every \(n\) only when \(d = 0\) and the sequence is constant.
From a recursive definition to an explicit formula
Given a recursive definition, write out the first few terms and guess an explicit formula. To prove the guess correct, either:
Method 1. Check that your guess gives the correct initial conditions and satisfies the recurrence relation.
Method 2. Use (strong) mathematical induction to prove that if \(a_0, a_1, a_2, \dots\) is the sequence defined by [the recursive definition], then [your guess].
Method 1 is the quicker one and Method 2 the rigorous one. Both are complete proofs; Method 1 leans on the fact that a recursive definition determines its sequence uniquely, which solving-recurrence-relations spells out.
Q3 of the pre-class questions
True or false? The sequence defined recursively as \(c_1 = 1\) and \(c_k = c_{k-1} + 2^k\) for each integer \(k \geq 2\) can be defined using the explicit formula \(c_n = 2^{\,n+1} - 3\) for each integer \(n \geq 1\).
True.
By Method 1
Label the two checks (i) and (ii). They are the two halves of the recursive definition.
(i) Initial conditions \((n=1)\): \(\;c_1 = 2^{1+1} - 3 = 2^2 - 3 = 4 - 3 = 1\) ✓
(ii) Recurrence relation:
\[\text{LHS} = c_k = 2^{k+1} - 3\] \[\text{RHS} = c_{k-1} + 2^k = 2^{(k-1)+1} - 3 + 2^k = 2^k + 2^k - 3 = 2\big(2^k\big) - 3 = 2^{k+1} - 3\]
so the explicit formula satisfies the given recurrence relation. Therefore the statement is true.
By Method 2
To prove that if \(c_1, c_2, c_3, \dots\) is the sequence defined by \(c_1 = 1\) and \(c_k = c_{k-1} + 2^k\) for each integer \(k \geq 2\), then \(c_n = 2^{\,n+1} - 3\) for each integer \(n \geq 1\) — by mathematical induction (PMI).
Let \(P(n)\) be the predicate \(c_n = 2^{\,n+1} - 3\).
Basis step. \(c_1 = 1\) by the recursive definition, and \(2^{1+1} - 3 = 4 - 3 = 1\), so the statement is true for \(n = 1\).
Inductive hypothesis. Suppose \(P(k)\) is true for some integer \(k \geq 1\). This means \(c_k = 2^{k+1} - 3\). Then
\[c_{k+1} = c_k + 2^{k+1} = 2^{k+1} - 3 + 2^{k+1} = 2\big(2^{k+1}\big) - 3 = 2^{k+2} - 3\]
Therefore \(P(k+1)\) is true. Hence by mathematical induction the sequence with the given recursive definition is defined explicitly as \(c_n = 2^{\,n+1} - 3\) for each integer \(n \geq 1\). \(\blacksquare\)
The recurrence is stated for \(k \geq 2\), so the substitution \(c_{k+1} = c_k + 2^{k+1}\) is legitimate for \(k \geq 1\) — the indices line up exactly with the basis step.
Worked: a recurrence with two initial conditions
Consider the sequence \(b_0 = 0\), \(b_1 = 1\) and \(b_k = \tfrac{1}{2}\big(b_{k-1} + b_{k-2} + 1\big) + 3(k-1)\) for each integer \(k \geq 2\).
(a) Calculate a few more terms and guess an explicit formula
\[b_2 = \tfrac{1}{2}(b_1 + b_0 + 1) + 3(1) = \tfrac{1}{2}(0 + 1 + 1) + 3 = 1 + 3 = 4\] \[b_3 = \tfrac{1}{2}(4 + 1 + 1) + 3(2) = 3 + 6 = 9\] \[b_4 = \tfrac{1}{2}(9 + 4 + 1) + 3(3) = 7 + 9 = 16\]
giving \(0, 1, 4, 9, 16, \dots\) — guess \(b_n = n^2\) for all integers \(n \geq 0\).
(b) Prove the guess by Method 1
Initial conditions \((n = 0\) and \(n = 1)\): \(\;b_0 = 0^2 = 0\) ✓ and \(b_1 = 1^2 = 1\) ✓ — so the explicit formula satisfies the initial conditions. Two initial conditions means two checks.
Recurrence relation. Suppose \(b_n = n^2\) for all \(n\):
\[\text{LHS} = b_k = k^2\]
\[\begin{aligned} \text{RHS} &= \tfrac{1}{2}\big((k-1)^2 + (k-2)^2 + 1\big) + 3(k-1) \\ &= \tfrac{1}{2}\big(k^2 - 2k + 1 + k^2 - 4k + 4 + 1\big) + 3k - 3 \\ &= \big(k^2 - 3k + 3\big) + 3k - 3 \\ &= k^2 \end{aligned}\]
\(\therefore\) LHS \(=\) RHS, so the explicit formula satisfies the recurrence relation. \(\blacksquare\)
The same result can be proved by strong induction — strong because the recurrence reaches back two terms, so \(P(k)\) alone would not be enough. See solving-recurrence-relations for that proof written out.
(c) Find a different recursive definition of the sequence
Look for a one-step recurrence \(b_n = b_{n-1} + p\) and solve for the step:
\[n^2 = (n-1)^2 + p \;\implies\; p = 2n - 1 \;\implies\; b_n = b_{n-1} + (2n-1)\]
Completed into a recursive definition, \(b_0 = 0\) with \(b_n = b_{n-1} + (2n-1)\) for \(n \geq 1\) gives the same sequence — the squares as running totals of the odd numbers. Two things to take from the exercise: a sequence does not have a unique recursive definition, and this one needs only one initial condition where the original needed two.
Worked: a recurrence with a fraction
Consider the sequence defined as \(d_0 = 1\) and \(d_k = \dfrac{d_{k-1}}{1 + d_{k-1}}\) for each integer \(k \geq 1\).
(a) Calculate a few more terms and guess an explicit formula
The trick used throughout is “\(\times 1\)”: multiply top and bottom by the denominator of the inner fraction to clear the compound fraction in one move.
\[d_1 = \frac{1}{1+1} = \frac{1}{2} \qquad d_2 = \frac{\tfrac{1}{2}}{1 + \tfrac{1}{2}} \cdot \frac{2}{2} = \frac{1}{2+1} = \frac{1}{3} \qquad d_3 = \frac{\tfrac{1}{3}}{1 + \tfrac{1}{3}} \cdot \frac{3}{3} = \frac{1}{3+1} = \frac{1}{4}\]
giving \(1, \tfrac12, \tfrac13, \tfrac14, \dots\) — guess \(d_n = \dfrac{1}{n+1}\).
(b) Prove the guess by Method 1
Initial condition \((d_0 = 1)\): \(\;d_0 = \dfrac{1}{0+1} = \dfrac{1}{1} = 1\) ✓
Recurrence relation. Suppose \(d_n = \dfrac{1}{n+1}\):
\[\text{LHS} = d_k = \frac{1}{k+1} \qquad\qquad \text{RHS} = \frac{d_{k-1}}{1 + d_{k-1}} = \frac{\tfrac{1}{k}}{1 + \tfrac{1}{k}} \cdot \frac{k}{k} = \frac{1}{k+1}\]
\(\therefore\) LHS \(=\) RHS, so the explicit formula satisfies the recurrence relation. \(\blacksquare\)
The same result can be proved by ordinary induction (MI) — ordinary this time, since the recurrence reaches back only one term.
The Tower of Hanoi
Given a tower of 8 discs in decreasing size on one of three pegs, transfer the entire tower to one of the other pegs, subject to: (a) move only one disc at a time; (b) never move a larger disc onto a smaller disc. Is there a solution? If so, what is the fewest number of moves?
For \(n \geq 1\) let \(m_n\) be the minimum number of moves to transfer a tower of \(n\) discs from one pole to another. Work up to the recurrence through three cases:
- \(n = 1\): one move, so \(m_1 = 1\).
- \(n = 2\): small disc to the spare peg, large disc across, small disc back on top — so \(m_2 = 3\).
- the general case: the whole transfer takes \(m_n\) moves and passes through four board positions, with the \(n-1\) smaller discs treated as one group. For four discs, \(m_4 = m_3 + 1 + m_3\).
The first two are shown below as sequences of board positions, each a transfer that takes that many moves. The recurrence is read off the general case.
Figure 2: The two small cases. One disc goes left peg to right peg in one move, and two discs take three, numbered \(1, 2, 3\), with the small disc parked on the middle peg in between. Each position is boxed and the green arrows are the moves. The middle move is forced: the large disc cannot move until the small one is off it and cannot land on the small one, so the spare peg has to be used, and that is what generalises to \(m_k = 2m_{k-1} + 1\).
In general:
\[m_1 = 1 \qquad\text{and}\qquad m_k = 2m_{k-1} + 1 \;\text{ for all integers } k \geq 2\]
The three stages between the four board positions take \(m_{n-1}\), \(m_1 = 1\) and \(m_{n-1}\) moves (drawn out in solving-recurrence-relations). The largest disc has to move at some point, and it can only move onto an empty peg — so the other \(k-1\) discs must first be stacked on the spare peg, and then moved back on top afterwards. Two sub-transfers plus one move.
Worked: proving the Tower of Hanoi formula
On page 310 (4th edition) or page 346 (5th edition) the textbook guesses \(m_n = 2^n - 1\) for all integers \(n \geq 1\). Prove the guess is correct by checking that it gives the correct initial conditions and satisfies the recurrence relation.
Suppose \(m_n = 2^n - 1\) for all \(n \in \mathbb{Z}^{+}\).
Initial condition \((m_1 = 1)\): \(\;m_1 = 2^1 - 1 = 2 - 1 = 1\) ✓
Recurrence relation \((m_k = 2m_{k-1} + 1)\):
\[\text{LHS} = m_k = 2^k - 1\] \[\text{RHS} = 2m_{k-1} + 1 = 2\big(2^{\,k-1} - 1\big) + 1 = 2 \cdot 2^{\,k-1} - 2 + 1 = 2^k - 1\]
So LHS \(=\) RHS \(\therefore\) the explicit formula satisfies the recurrence relation. \(\blacksquare\)
The textbook proves the same result by mathematical induction (PMI) instead — so this is Method 1 versus Method 2 on the same problem one more time.
The eight-disc puzzle of the problem statement needs \(2^8 - 1 = 255\) moves, and “is there a solution?” is answered constructively, because the recurrence is the algorithm.
See also
- solving-recurrence-relations — the reference note for all of the above
- recursive-definitions · sequences-and-summations · mathematical-induction · strong-induction-and-the-well-ordering-principle
- 2026-08-31-recursive-definitions — Lecture 15
- 2026-09-03-set-theory-definitions — Lecture 17
- practice-problems — §20 Solving Recurrence Relations, with full worked solutions