Recurrences

Recurrences, or recurrence relations, are equations that define sequences by relating each term to one or more previous terms. A recurrence typically specifies the value of the nth term in terms of the preceding k terms, together with initial conditions that supply the first k terms. The order is the number of prior terms involved, and the coefficients determine how those terms combine.

They can be linear or nonlinear; linear recurrences have terms that are linear combinations of previous terms. They are homogeneous when the recurrence has no nonzero term independent of the sequence, and non-homogeneous otherwise. Recurrences may have constant coefficients (the coefficients do not depend on n) or variable coefficients.

Solve methods: For linear homogeneous recurrences with constant coefficients, solutions are found by solving a characteristic equation; the roots yield a closed-form expression. Generating functions turn recurrences into algebraic equations in a formal power series. Another approach is iterative expansion, or, for certain recurrences encountered in algorithms, applying the Master Theorem or recursion trees to obtain growth rates.

Example: the Fibonacci sequence is defined by F(n) = F(n-1) + F(n-2) with initial values F(0)=0 and F(1)=1. This linear constant-coefficient recurrence has a closed-form solution and grows exponentially with n, at a rate proportional to the golden ratio to the nth power.

Applications: Recurrences model algorithm running times, dynamic programming solutions, combinatorial counts, and population or economic models. They provide a framework for analyzing discrete processes and for designing efficient algorithms through iterative or recursive formulations.