MODULE 15
Recurrence Relations
First-Order: an = r·an-1 + d
Second-Order: an = c1an-1 + c2an-2
Example: Fibonacci is an=an-1+an-2 with a0=0, a1=1 (c1=1, c2=1) — try the defaults above.
Understanding Recurrence Relations
A recurrence relation defines each term of a sequence in terms of earlier terms, like the Fibonacci sequence where each number is the sum of the two before it. Solving a recurrence means finding a direct (closed-form) formula that computes any term without needing all the previous ones — essential for analyzing how fast recursive algorithms run.
Key Definitions & Formulas
- Recurrence relation: a rule like an = an-1 + an-2, plus base case(s).
- Closed-form solution: a direct formula for an not requiring earlier terms.
- Characteristic equation: for linear recurrences, substituting an = rn turns the recurrence into a polynomial equation whose roots determine the closed form.
- Master theorem: gives closed-form time complexity for divide-and-conquer recurrences like T(n) = aT(n/b) + f(n).
Worked Example
For an = 5an-1 - 6an-2, the characteristic equation is r² - 5r + 6 = 0, which factors to (r-2)(r-3) = 0, giving roots r = 2 and r = 3. The closed form is therefore an = C₁·2n + C₂·3n, with constants found from the base cases.
Where This Is Used
- Analyzing recursive algorithm runtime (e.g. merge sort's T(n) = 2T(n/2) + n).
- Population growth and financial compound-interest models.
- Dynamic programming, which is fundamentally about efficiently evaluating a recurrence.
- Fractal geometry and self-similar structure analysis.