Linear Recurrence Equation

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).

Wolfram Web Resources