• Overview
• Details
• Exercises

Recurrence relations define sequences by referencing previous terms. They arise in algorithms (divide-and-conquer), combinatorics, and discrete math. Common solution tools include iteration, characteristic equations, generating functions, and the Master Theorem.

• Linear recurrences with constant coefficients: solve via characteristic polynomial; handle repeated roots and inhomogeneous terms with particular solutions.
• Divide-and-conquer: T(n) = a T(n/b) + f(n). Use Master Theorem cases and recursion-tree/AKRA–BAZZI where needed.
• Iteration/unrolling: expand a few levels and identify patterns.
• Generating functions: encode sequence, manipulate algebraically, then extract coefficients.
• Boundary conditions: initial terms determine constants; ensure domains (n ≥ n0).

1. Solve a Fibonacci-like recurrence: a(n) = 3a(n-1) - 2a(n-2), with a(0)=0, a(1)=1.
2. Apply the Master Theorem to T(n) = 2T(n/2) + n log n and to T(n) = 3T(n/3) + n.
3. Use generating functions to solve a(n) - a(n-1) = 2^n with a(0)=0.