Solving recurrence relations
A recurrence tells you how each term depends on earlier ones. Solving it gives a direct formula, revealing how fast the sequence grows.
Why solve recurrences?
Recurrences arise naturally from recursive algorithms and growth processes. A closed form lets you compute any term directly and compare growth rates. For example, knowing merge sort satisfies \(T(n) = 2T(n/2) + n\) and that this solves to \(n\log_2 n\) explains why it is fast.
Iteration (unrolling)
Substitute the recurrence into itself repeatedly and look for a pattern. For \(a_n = a_{n-1} + 3\) with \(a_0 = 5\): \(a_n = a_{n-2} + 6 = \cdots = 5 + 3n\). For \(a_n = 2a_{n-1}\) with \(a_0 = 1\): \(a_n = 2^n\). Then confirm the guess by induction.
Linear homogeneous recurrences
For \(a_n = c_1a_{n-1} + c_2a_{n-2}\), try \(a_n = r^n\). This gives the characteristic equation \(r^2 = c_1r + c_2\). If it has distinct roots \(r_1, r_2\), the solution is \(a_n = \alpha r_1^n + \beta r_2^n\), with constants from the initial conditions.
r^2 - c_1 r - c_2 = 0Worked example: Fibonacci
Fibonacci's characteristic equation is \(r^2 = r + 1\), with roots \(\phi = \frac{1 + \sqrt{5}}{2} \approx 1.618\) and \(\frac{1 - \sqrt{5}}{2}\). The resulting Binet formula is \(F_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}\). Fibonacci numbers grow like \(\phi^n\), and the ratio of consecutive terms approaches the golden ratio.
F_n = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}Worked example: a repeated root
For \(a_n = 4a_{n-1} - 4a_{n-2}\), the characteristic equation \(r^2 - 4r + 4 = 0\) has a repeated root \(r = 2\). The solution form becomes \(a_n = (\alpha + \beta n)2^n\). With \(a_0 = 1\), \(a_1 = 4\): \(\alpha = 1\) and \(2(1 + \beta) = 4\), so \(\beta = 1\), giving \(a_n = (1 + n)2^n\).
Divide-and-conquer recurrences
Algorithms that split a problem into \(a\) subproblems of size \(n/b\) with extra work \(f(n)\) satisfy \(T(n) = aT(n/b) + f(n)\). The master theorem gives the answer for common forms: binary search, \(T(n) = T(n/2) + 1\), gives \(O(\log n)\); merge sort, \(T(n) = 2T(n/2) + n\), gives \(O(n\log n)\).
Non-homogeneous recurrences
When a recurrence has an extra term, such as \(a_n = 2a_{n-1} + 1\), find one particular solution (here the constant \(-1\)) and add the homogeneous solution \(\alpha 2^n\). With \(a_0 = 0\), \(a_n = 2^n - 1\), matching the Towers of Hanoi.
Common mistakes
Forgetting initial conditions, which leaves unknown constants. Mishandling repeated roots. Guessing a pattern without proving it. Confusing the number of subproblems with their size in divide-and-conquer recurrences.
Key takeaways
Unroll simple recurrences and prove the pattern by induction. Linear homogeneous recurrences use the characteristic equation; repeated roots add a factor of \(n\). Fibonacci grows like the golden ratio. Divide-and-conquer recurrences are solved by the master theorem.
Flashcard
A direct formula for the nth term
Check your understanding
What is the closed form of a_n = a_(n-1) + 4 with a_0 = 2?