TOPICS

Linear Recurrence Equation

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

A linear recurrence equation is a recurrence equation on a sequence of numbers {x_n} expressing x_n as a first-degree polynomial in x_k with k<n. For example

x_n=Ax_(n-1)+Bx_(n-2)+Cx_(n-3)+....
(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 n obtained by iterating the linear recurrence with kernel ker starting with initial values init, where for example a kernel {c_1,c_2} denotes the recurrence relation a_n=c_1a_(n-1)+c_2a_(n-2) and the initial values are {a_1,a_2,...}. 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 n based on solving specified the recurrence equations.

The following table summarizes some common linear recurrence equations and the corresponding solutions.

recurrenceinitial conditionssolution
a_n=a_(n-1)+a_(n-2)a_1=a_2=1Fibonacci number F_n
a_n=a_(n-1)+a_(n-2)a_1=1, a_2=3Lucas number L_n
a_n=a_(n-2)+a_(n-3)a_0=a_1=a_2=1Padovan sequence P_n
a_n=2a_(n-1)+a_(n-2)a_0=0, a_1=1Pell number P_n
a_n=2a_(n-1)+a_(n-2)a_0=a_1=2Pell-Lucas number Q_n
a_n=a_(n-2)+a_(n-3)a_0=3, a_1=0, a_2=2Perrin sequence P_n

The general second-order linear recurrence equation

x_n=Ax_(n-1)+Bx_(n-2)
(2)

for constants A and B with arbitrary x_1 and x_2 has terms

x_1=x_1
(3)
x_2=x_2
(4)
x_3=Bx_1+Ax_2
(5)
x_4=Bx_2+ABx_1+A^2x_2
(6)
x_5=B^2x_1+2ABx_2+A^2Bx_1+A^3x_2
(7)
x_6=B^2x_2+2AB^2x_1+3A^2Bx_2+A^3Bx_1+A^4x_2
(8)
x_7=B^3x_1+4A^3Bx_2+3A^2B^2x_1+3AB^2x_2+A^4Bx_1+A^5x_2.
(9)

Therefore, an arbitrary term can be written as

x_n=sum_(k=0)^(n-2)(|_1/2(n+k-2)_|; k)A^kB^(|_(n-k-1)/2_|)x_1^([n+k (mod 2)])x_2^([n+k+1 (mod 2)])
(10)
=-(Ax_1-x_2)sum_(k=0)^(n-2)A^(2k-n+2)B^(-k+n-2)(k; n-k-2)+x_1sum_(k=0)^(n-1)A^(2k-n+1)B^(-k+n-1)(k; n-k-1).
(11)

If x_1=x_2=1, then the closed form for x_n is given by

x_n=(alpha^nbeta(1-beta)-beta^nalpha(1-alpha))/(alphabeta(alpha-beta)),
(12)

where alpha and beta are the roots of the quadratic equation

x^2-Ax-B=0,
(13)
alpha=1/2(A+sqrt(A^2+4B))
(14)
beta=1/2(A-sqrt(A^2+4B)).
(15)

If instead x_1=1 and x_2=A, the solution becomes

x_n=(alpha^n-beta^n)/(alpha-beta).
(16)

For example, the Fibonacci numbers F_n which are equal to 1, 1, 2, 3, 5, 8, ... for n=1, 2, ..., have A=B=1, so alpha=(1+sqrt(5))/2 and beta=(1-sqrt(5))/2, giving

F_n=([1/2(1+sqrt(5))]^n-[1/2(1-sqrt(5))]^n)/(sqrt(5))
(17)
=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^nsqrt(5)).
(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

f_n=f_(n-1)+f_(n-2)
(19)

with f_1=a and f_2=b has solution by

f_n=1/2[(3a-b)F_n+(b-a)L_n],
(20)

where F_n is a Fibonacci number and L_n is a Lucas number.

Any sequence b(n) satisfying the two-term recurrence equation

b(n)=b(n-1)-b(n-2)
(21)

can be written as

b(n)=b(0)a(n)+[b(1)-b(0)]a(n-1),
(22)

where

a(n)=U_n(1/2)
(23)
=2/3sqrt(3)sin(1/3(n+1)pi)
(24)

is the sequence of coefficients in the Maclaurin series for 1/Phi_6(x), where Phi_6(x) is a cyclotomic polynomial (OEIS A010892) and U_n(z) is a Chebyshev polynomial of the second kind.

A linear second-order recurrence

f_(n+1)=xf_n+yf_(n-1)
(25)

can be solved rapidly using a "rate doubling,"

f_(n+2)=(x^2+2y)f_n-y^2f_(n-2),
(26)

"rate tripling"

f_(n+3)=(x^3+3xy)f_n+y^3f_(n-3),
(27)

or, in general, "rate k-tupling" formula

f_(n+k)=p_kf_n+q_kf_(n-k),
(28)

where

p_0=2
(29)
p_1=x
(30)
p_k=2(-y)^(k/2)T_k(x/(2isqrt(y)))
(31)
p_(k+1)=xp_k+yp_(k-1)
(32)

(here, T_k(x) is a Chebyshev polynomial of the first kind) and

q_0=-1
(33)
q_1=y
(34)
q_k=-(-y)^k
(35)
q_(k+1)=-yq_k
(36)

(Gosper and Salamin 1972).

The general linear third-order recurrence equation

x_n=Ax_(n-1)+Bx_(n-2)+Cx_(n-3)
(37)

has solution

x_n=x_1((alpha^(-n))/(A+2alphaB+3alpha^2C)+(beta^(-n))/(A+2betaB+3beta^2C)+(gamma^(-n))/(A+2gammaB+3gamma^2C)) -(Ax_1-x_2)((alpha^(1-n))/(A+2alphaB+3alpha^2C)+(beta^(1-n))/(A+2betaB+3beta^2B)+(gamma^(1-n))/(A+2gammaC+3gamma^2C)) -(Bx_1+Ax_2-x_3)((alpha^(2-n))/(A+2alphaB+3alpha^2C)+(beta^(2-n))/(A+2betaB+3beta^2C)+(gamma^(2-n))/(A+2gammaB+3gamma^2C)),
(38)

where alpha, beta, and gamma are the roots of the polynomial

Cx^3+Bx^2+Ax=1.
(39)

For a finite linear recurrence sequence of functions

s_i(x)=A_i(x)s_(i+1)(x)+B_i(x),
(40)

where i=1, ..., r-1, and s_r(x)=h(x), then

s_1(x)=|B_1(x) -A_1(x) 0 ... 0; B_2(x) 1 -A_2(x) ... 0; B_3(x) 0 1 ... |; | | ... ... 0; B_(r-1)(x) 0 0 ... -A_(r-1)(x); h(x) 0 0 ... 1|
(41)

(Mansour 2000).

See also

Binet's Formula, Integer Sequence, Quadratic Map, Quadratic Recurrence Equation, Recurrence Equation

Explore with Wolfram|Alpha

References

Gosper, R. W. and Salamin, E. Item 14 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 8-9, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html#item14.Grosjean, C. C. In Topics in Polynomials of One and Several Variables and Their Applications: Volume Dedicated to the Memory of P.L. Chebyshev (1821-1894) (Ed. T. M. Rassias, H. M. Srivastava, and A. Yanushauskas). Singapore: World Scientific, 1993.Mansour, T. "Permutations Avoiding a Pattern from S_k and at Least Two Patterns from S_3." 31 Jul 2000. http://arxiv.org/abs/math.CO/0007194.Sloane, N. J. A. Sequence A010892 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Linear Recurrence Equation

Cite this as:

Weisstein, Eric W. "Linear Recurrence Equation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LinearRecurrenceEquation.html

Subject classifications