A linear recurrence equation is a recurrence equation on a sequence of numbers expressing as a first-degree polynomial in with . For example
(1)
|
A quotient-difference table eventually yields a line of 0s iff the starting sequence is defined by a linear recurrence equation.
The Wolfram Language command LinearRecurrence[ker, init, n] gives the sequence of length obtained by iterating the linear recurrence with kernel ker starting with initial values init, where for example a kernel denotes the recurrence relation and the initial values are . FindLinearRecurrence[list] attempts to find a minimal linear recurrence that generates list. RecurrenceTable[eqns, expr, n, nmax] generates a list of values of expr for successive based on solving specified the recurrence equations.
The following table summarizes some common linear recurrence equations and the corresponding solutions.
recurrence | initial conditions | solution |
Fibonacci number | ||
, | Lucas number | |
Padovan sequence | ||
, | Pell number | |
Pell-Lucas number | ||
, , | Perrin sequence |
The general second-order linear recurrence equation
(2)
|
for constants and with arbitrary and has terms
(3)
| |||
(4)
| |||
(5)
| |||
(6)
| |||
(7)
| |||
(8)
| |||
(9)
|
Therefore, an arbitrary term can be written as
(10)
| |||
(11)
|
If , then the closed form for is given by
(12)
|
where and are the roots of the quadratic equation
(13)
|
(14)
| |||
(15)
|
If instead and , the solution becomes
(16)
|
For example, the Fibonacci numbers which are equal to 1, 1, 2, 3, 5, 8, ... for , 2, ..., have , so and , giving
(17)
| |||
(18)
|
Grosjean (1993) discusses how to rewrite such "difference of powers of roots" solutions in explicit integer form.
A generalized version of Fibonacci numbers has recurrence
(19)
|
with and has solution by
(20)
|
where is a Fibonacci number and is a Lucas number.
Any sequence satisfying the two-term recurrence equation
(21)
|
can be written as
(22)
|
where
(23)
| |||
(24)
|
is the sequence of coefficients in the Maclaurin series for , where is a cyclotomic polynomial (OEIS A010892) and is a Chebyshev polynomial of the second kind.
A linear second-order recurrence
(25)
|
can be solved rapidly using a "rate doubling,"
(26)
|
"rate tripling"
(27)
|
or, in general, "rate -tupling" formula
(28)
|
where
(29)
| |||
(30)
| |||
(31)
| |||
(32)
|
(here, is a Chebyshev polynomial of the first kind) and
(33)
| |||
(34)
| |||
(35)
| |||
(36)
|
(Gosper and Salamin 1972).
The general linear third-order recurrence equation
(37)
|
has solution
(38)
|
where , , and are the roots of the polynomial
(39)
|
For a finite linear recurrence sequence of functions
(40)
|
where , ..., , and , then
(41)
|
(Mansour 2000).