Recurrence Relations

Defining Recurrence Relations

A recurrence relation defines each term of a sequence using earlier terms, paired with initial conditions to start. Without initial conditions, the sequence is undetermined, just like a recursive function without a base case.

To unfold a recurrence, you compute it forward from the initial conditions. A closed form is a direct formula for $F(n)$ avoiding earlier terms, such as $a(n) = 2^n$ for $a(n) = 2\,a(n-1)$ with $a(0) = 1$.

Why Recurrences Matter

Recurrences model processes building on previous states, mirroring recursion in programming. They are central to algorithm analysis, describing running times like $T(n) = 2\,T(n/2) + n$.

Common Pitfall: Supplying too few initial conditions. A recurrence reaching back $k$ steps needs $k$ starting values. $F(n) = F(n-1) + F(n-2)$ requires two starting values, or the sequence remains undefined.