Recurrence

Recurrence refers to a relation that defines a sequence by relating each term to previous terms. A recurrence relation consists of an equation that expresses a term as a function of earlier terms and possibly of the index n, together with initial conditions that provide starting values.

Common classes include linear versus nonlinear recurrences, homogeneous versus nonhomogeneous, and fixed-order recurrences where the kth term depends on the k−1 previous terms. A linear homogeneous recurrence of order d has the form a_n = c1 a_{n-1} + c2 a_{n-2} + ... + cd a_{n-d}, with constants ci. Nonlinear recurrences involve nonlinear functions of previous terms. The Fibonacci sequence, defined by F_n = F_{n-1} + F_{n-2} with F_0 = 0 and F_1 = 1, is a well-known example.

Solutions are sought as explicit formulas or representations. For linear recurrences with constant coefficients, the characteristic equation r^d = c1 r^{d-1} + ... + cd yields roots that determine the general solution. Generating functions and matrix methods provide alternative solving techniques. Some recurrences are analyzed asymptotically or through estimation methods.

Applications are widespread. In mathematics, recurrences appear in combinatorics, number theory, and analysis. In computer science, they model algorithms and data structures, with running times expressed as recurrences that can often be solved by the Master theorem or related techniques. In the sciences, populations, financial time series, and other dynamic processes are frequently modeled by recurrence or autoregressive relations.