A linear recurrence relation expresses each term of a sequence as a linear combination of earlier terms, possibly with an added forcing term. A constant-coefficient homogeneous recurrence of order has the form
Together with consecutive initial conditions, it determines the following terms uniquely. For example, the Fibonacci sequence satisfies , , .
Substituting gives the characteristic polynomial of a linear recurrence. Distinct characteristic roots give independent geometric solutions; repeated roots introduce factors polynomial in . This converts repeated term-by-term computation into polynomial or matrix arithmetic, useful for obtaining a distant term efficiently.
A second-order linear recurrence relation normally uses two consecutive initial conditions, but two specified nonconsecutive values may also determine a unique solution of the linear recurrence relation. For two independent homogeneous solutions of the linear recurrence relation , the coefficients in are determined by exactly when . Otherwise the data can be inconsistent or can leave freedom. A nonconsecutive subscript is therefore not by itself evidence of an error.
For a repeated characteristic root of a linear recurrence , use , . The determinant is for distinct , so any such pair of prescribed values determines the two coefficients.
For , subtract the equilibrium to get . Hence . For , the solution is . The exceptional factor in a formula with is avoided by retaining the given initial value.
A linear recurrence matrix advances a vector of quantities by a fixed linear map: , hence . It can encode several simultaneous linear recurrences and need not satisfy the normalization required of a Markov chain transition matrix.
For fixed parameters , the two Lucas sequences are the solutions of the linear recurrence relation with initial values and . They are the Lucas U-sequence and the Lucas V-sequence. The choice gives the Fibonacci sequence and the ordinary Lucas numbers.
If are distinct roots of , direct substitution gives and . The recurrence itself remains meaningful when the roots coincide or division is unavailable, so it is the safest definition over a general ring. Fast doubling for Lucas sequences exploits these two related solutions to compute distant terms.
The Lucas V-sequence has , and . Thus its first terms are . For these are the Lucas numbers .
For roots of , one has , including the repeated-root case. This gives immediately. The identity relates it to the Lucas U-sequence without requiring division.
The Lucas U-sequence has , and . Its first terms are . At it is the Fibonacci sequence.
If the roots of its characteristic polynomial of a linear recurrence are distinct, . This identity follows by checking the two initial conditions and the linear recurrence relation. At a repeated root , the corresponding formula is for .
Lucas sequences satisfy
These identities follow from the root formulas for the Lucas U-sequence and Lucas V-sequence, or from their recurrence, so they are polynomial identities valid over a commutative ring. They compute terms with doubled indices from terms with about half the index.
A division-free algorithm carries . Put , , and . For an even target return ; for an odd target return . Starting from and following the binary digits of the target uses ring operations. At this is the usual Fibonacci doubling method, and it also works in modular arithmetic.
For the constant-coefficient homogeneous linear recurrence relation , its characteristic polynomial is
A nonzero root gives the solution . Over a field of characteristic zero, a root of multiplicity contributes when . The Fibonacci sequence has , whose roots give its familiar closed formula.
Equivalently, annihilates the shift on every solution. Reducing modulo therefore expresses the distant term as a linear combination of . Repeated squaring in the polynomial quotient ring gives this combination using logarithmically many multiplications in .
The Kitamasa algorithm evaluates a term of an order- linear recurrence by reducing powers of modulo its characteristic polynomial of a linear recurrence. If the recurrence relation is , reduce modulo by exponentiation by squaring; the resulting coefficients give as a linear combination of . Straightforward polynomial multiplication gives arithmetic operations.
For two solutions of the linear recurrence relation , their discrete Wronskian obeys . Substitute the recurrence into : the terms cancel and the remaining expression is . Iteration gives , including when some vanish. A nonzero discrete Wronskian proves linear independence of the two solutions.
An inhomogeneous linear recurrence has a prescribed forcing sequence rather than zero on the right. The difference of two solutions satisfies the associated homogeneous linear recurrence relation, so every solution is a particular solution plus a homogeneous solution.
The unit-response sequence , is six-periodic. In the displayed convolution, all older terms cancel under by this recurrence; the two new boundary terms reduce to . Thus it gives a particular solution of the inhomogeneous linear recurrence with forcing . Add the two-dimensional homogeneous span of and for the general solution. This is a discrete Green function construction.
Let be the forward shift on sequences and the polynomial defining a constant-coefficient linear recurrence relation. For a nonzero base , , so is a particular solution when . At a simple root of the characteristic equation of a linear recurrence, the correct trial acquires a factor :
The identity follows by substituting into each shift term. A root of multiplicity analogously requires a degree- polynomial factor; the lower-degree homogeneous terms are supplied by the repeated characteristic root of a linear recurrence.
A variable-coefficient affine recurrence is a linear recurrence relation with coefficients allowed to depend on the index. If every is nonzero, a discrete integrating factor reduces it to a telescoping series.
For , put and , with . Dividing by this accumulated homogeneous growth gives and . A telescoping series then proves
This is the discrete counterpart of the integrating factor for a first-order linear differential equation.
For a constant-coefficient linear recurrence relation, substituting a trial sequence produces a polynomial equation in called its characteristic equation. Repeated roots contribute factors polynomial in .
For a constant-coefficient linear recurrence relation over the complex numbers, a nonzero root of multiplicity in its characteristic polynomial of a linear recurrence supplies the linearly independent solutions
Substitute . Each factor of the shift linear operator becomes times the forward difference operator on , so its th power kills every polynomial in of degree less than . Their independence follows from the Lagrange root bound over a field. The same argument works over a field of characteristic zero; the displayed monomials need modification in positive characteristic.
A zero root needs separate initial-data treatment: for characteristic polynomial , the recurrence relation is , leaving the first values arbitrary.
For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots , the solution is . If , boundedness for forces , and fixes . This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor .
For a sequence , its ordinary generating function is the formal power series
A constant-coefficient linear recurrence relation turns into an algebraic equation for after multiplication by powers of and summation; the initial values supply the correction polynomial. For example, if , and , then
Hence is a rational function, interpreted as a formal power series at zero. No analytic convergence is needed. Variable coefficients can instead lead to operations such as differentiation, so the constant-coefficient hypothesis is part of this rational-function conclusion.
The ordinary generating function of the sequence is
The floor function takes the same value at and . Grouping those adjacent terms gives
which simplifies to the displayed expression. The middle identity follows by differentiating the geometric series. The calculation is valid as an identity of formal power series, or analytically for .
Expanding begins , making the paired values of the sequence visible in the coefficients.
An affine recurrence on a finite-dimensional vector space has the form , where is a fixed linear operator and a fixed vector. Induction gives
The sum is empty at . If is invertible, the unique fixed point is , and subtracting it reduces the recurrence to . The sum formula remains valid when is singular, even when no fixed point exists. For example, gives the arithmetic progression . A stable affine recurrence additionally has spectral radius below one and converges to its fixed point.
If the spectral radius of is below one, converges to the unique fixed point .

Ancestors (4)

  1. Algebra
  2. Area of mathematics
  3. Mathematics
  4. Home

Synonyms (1)

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.