Linear recurrence

A linear recurrence with constant coefficients is an equation of the form a_n = c₁ a_n−1 + c₂ a_n−2 + … + c_k a_n−k for n ≥ k, where the c_i are constants and k is the order. The recurrence is homogeneous if the right-hand side has no additional term; otherwise it is nonhomogeneous. The first k values (initial conditions) uniquely determine the entire sequence. For example, the Fibonacci numbers satisfy F_n = F_n−1 + F_n−2 with F₀=0, F₁=1, a second-order linear recurrence.¹²

The characteristic polynomial of a homogeneous linear recurrence is p(x) = x^k − c₁ x^k−1 − … − c_k. Its roots determine the general solution: if the roots r₁, … , r_k are distinct, the sequence is a_n = α₁ r₁ⁿ + … + α_k r_kⁿ, where the α_i are constants fixed by initial conditions. Repeated roots introduce polynomial factors. For nonhomogeneous recurrences, a particular solution is added. This method is equivalent to solving a linear difference equation and is closely related to generating functions and the z-transform.³⁴

Linear recurrences appear in combinatorial sequences (e.g., Fibonacci, Lucas, Pell numbers), analysis of algorithms (e.g., time complexity of divide-and-conquer algorithms like merge sort can be expressed as recurrences), population modeling, and signal processing. The linear recurrence is also used in cryptography (linear feedback shift registers) and in the study of continued fractions. In computer science, dynamic programming solutions often reduce to evaluating linear recurrences efficiently using matrix exponentiation.¹⁵

Beyond the standard theory, linear recurrences have deep connections to linear algebra: the companion matrix of the recurrence has eigenvalues equal to the roots of the characteristic polynomial. The matrix exponentiation method computes the nth term in O(k³ log n) time. For recurrences modulo a prime, the periodicity (Pisano period for Fibonacci) is studied. The generating function of a linear recurrence is a rational function, and the recurrence can be recovered from its denominator. The Skolem–Mahler–Lech theorem describes the set of zeros of a linear recurrence sequence. Also, linear recurrences with polynomial coefficients (linear difference equations) are far more complex and arise in special functions.²⁶

Order

The number of previous terms used in the recurrence.

Characteristic polynomial

The polynomial p(x) = x^k - c_1 x^{k-1} - ... - c_k, whose roots determine the solution form.

Homogeneous recurrence

A recurrence with no constant term; all terms are linear combinations of previous terms.