recurrència

Recurrència is a relation that defines a sequence by expressing each term as a function of one or more preceding terms. The order of a recurrence is the number of previous terms needed to determine the next one. Recurrences can be linear or nonlinear, homogeneous or nonhomogeneous, and may be defined over integers, real numbers, or other structures.

A common example is the Fibonacci recurrence: F(n) = F(n-1) + F(n-2), with initial values F(0) = 0 and F(1) = 1. More generally, linear recurrences take the form a(n) = c1 a(n-1) + c2 a(n-2) + ... + ck a(n-k) + g(n), where the constants ci determine the dependency on previous terms and g(n) is a nonhomogeneous part. The behavior of a sequence is often studied through its order, initial conditions, and the nature of the coefficients.

Solving recurrences means finding an explicit formula for a(n) or characterizing its growth. Linear homogeneous recurrences with constant coefficients have solutions that are linear combinations of terms r^n, where r are the roots of the characteristic polynomial obtained from the recurrence. Nonhomogeneous cases are handled by finding a particular solution and adding it to the general solution of the corresponding homogeneous part. Techniques include iterative expansion, generating functions, and, in some contexts, the Z-transform or matrix methods.

Recurrences appear in diverse areas such as algorithm analysis, where running times are modeled by recurrences; in dynamic programming; and in combinatorics and population models. They provide a framework for describing stepwise processes and for deriving exact or asymptotic behavior of sequences.