In mathematics (including combinatorics, linear algebra, and dynamical systems), a linear recurrence with constant coefficients (also known as a linear recurrence relation or linear difference equation) sets equal to 0 a polynomial that is linear in the various iterates of a variable—that is, in the values of the elements of a sequence. The polynomial's linearity means that each of its terms has degree 0 or 1. A linear recurrence denotes the evolution of some variable over time, with the current time period or discrete moment in time denoted as t, one period earlier denoted as t − 1, one period later as t + 1, etc. The solution of such an equation is a function of t, and not of any iterate values, giving the value of the iterate at any time. To find the solution it is necessary to know the specific values (known as initial conditions) of n of the iterates, and normally these are the n iterates that are oldest. The equation or its variable is said to be stable if from any set of initial conditions the variable's limit as time goes to infinity exists; this limit is called the steady state. Difference equations are used in a variety of contexts, such as in economics to model the evolution through time of variables such as gross domestic product, the inflation rate, the exchange rate, etc. They are used in modeling such time series because values of these variables are only measured at discrete intervals. In econometric applications, linear difference equations are modeled with stochastic terms in the form of autoregressive (AR) models and in models such as vector autoregression (VAR) and autoregressive moving average (ARMA) models that combine AR with other features.
Definitions A linear recurrence with constant coefficients is an equation of the following form, written in terms of parameters a1, ..., an and b:
y t = a 1 y t − 1 + ⋯ + a n y t − n + b , {\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b,}
or equivalently as
y t + n = a 1 y t + n − 1 + ⋯ + a n y t + b . {\displaystyle y_{t+n}=a_{1}y_{t+n-1}+\cdots +a_{n}y_{t}+b.}
The positive integer n {\displaystyle n} is called the order of the recurrence and denotes the longest time lag between iterates. The equation is called homogeneous if b = 0 and nonhomogeneous if b ≠ 0. If the equation is homogeneous, the coefficients determine the characteristic polynomial (also "auxiliary polynomial" or "companion polynomial")
p ( λ ) = λ n − a 1 λ n − 1 − a 2 λ n − 2 − ⋯ − a n {\displaystyle p(\lambda )=\lambda ^{n}-a_{1}\lambda ^{n-1}-a_{2}\lambda ^{n-2}-\cdots -a_{n}}
whose roots play a crucial role in finding and understanding the sequences satisfying the recurrence.
Conversion to homogeneous form If b ≠ 0, the equation
y t = a 1 y t − 1 + ⋯ + a n y t − n + b {\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}
is said to be nonhomogeneous. To solve this equation it is convenient to convert it to homogeneous form, with no constant term. This is done by first finding the equation's steady state value—a value y* such that, if n successive iterates all had this value, so would all future values. This value is found by setting all values of y equal to y* in the difference equation, and solving, thus obtaining
y ∗ = b 1 − a 1 − ⋯ − a n {\displaystyle y^{*}={\frac {b}{1-a_{1}-\cdots -a_{n}}}}
assuming the denominator is not 0. If it is zero, the steady state does not exist. Given the steady state, the difference equation can be rewritten in terms of deviations of the iterates from the steady state, as
( y t − y ∗ ) = a 1 ( y t − 1 − y ∗ ) + ⋯ + a n ( y t − n − y ∗ ) {\displaystyle \left(y_{t}-y^{*}\right)=a_{1}\left(y_{t-1}-y^{*}\right)+\cdots +a_{n}\left(y_{t-n}-y^{*}\right)}
which has no constant term, and which can be written more succinctly as
x t = a 1 x t − 1 + ⋯ + a n x t − n {\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}
where x equals y − y*. This is the homogeneous form. If there is no steady state, the difference equation
y t = a 1 y t − 1 + ⋯ + a n y t − n + b {\displaystyle y_{t}=a_{1}y_{t-1}+\cdots +a_{n}y_{t-n}+b}
can be combined with its equivalent form
y t − 1 = a 1 y t − 2 + ⋯ + a n y t − ( n + 1 ) + b {\displaystyle y_{t-1}=a_{1}y_{t-2}+\cdots +a_{n}y_{t-(n+1)}+b}
to obtain (by solving both for b)
y t − a 1 y t − 1 − ⋯ − a n y t − n = y t − 1 − a 1 y t − 2 − ⋯ − a n y t − ( n + 1 ) {\displaystyle y_{t}-a_{1}y_{t-1}-\cdots -a_{n}y_{t-n}=y_{t-1}-a_{1}y_{t-2}-\cdots -a_{n}y_{t-(n+1)}}
in which like terms can be combined to give a homogeneous equation of one order higher than the original.
Solution example for small orders The roots of the characteristic polynomial play a crucial role in finding and understanding the sequences satisfying the recurrence. If there are d {\displaystyle d} distinct roots r 1 , r 2 , … , r d , {\displaystyle r_{1},r_{2},\ldots ,r_{d},} then each solution to the recurrence takes the form
a n = k 1 r 1 n + k 2 r 2 n + ⋯ + k d r d n , {\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}
where the coefficients k i {\displaystyle k_{i}} are determined in order to fit the initial conditions of the recurrence. When the same roots occur multiple times, the terms in this formula corresponding to the second and later occurrences of the same root are multiplied by increasing powers of n {\displaystyle n} . For instance, if the characteristic polynomial can be factored as ( x − r ) 3 {\displaystyle (x-r)^{3}} , with the same root r {\displaystyle r} occurring three times, then the solution would take the form
a n = k 1 r n + k 2 n r n + k 3 n 2 r n . {\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}
Order 1 For order 1, the recurrence
a n = r a n − 1 {\displaystyle a_{n}=ra_{n-1}}
has the solution a n = r n {\displaystyle a_{n}=r^{n}} with a 0 = 1 {\displaystyle a_{0}=1} and the most general solution is a n = k r n {\displaystyle a_{n}=kr^{n}} with a 0 = k {\displaystyle a_{0}=k} . The characteristic polynomial equated to zero (the characteristic equation) is simply t − r = 0 {\displaystyle t-r=0} .
Order 2 Solutions to such recurrence relations of higher order are found by systematic means, often using the fact that a n = r n {\displaystyle a_{n}=r^{n}} is a solution for the recurrence exactly when t = r {\displaystyle t=r} is a root of the characteristic polynomial. This can be approached directly or using generating functions (formal power series) or matrices. Consider, for example, a recurrence relation of the form
a n = A a n − 1 + B a n − 2 . {\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}
When does it have a solution of the same general form as a n = r n {\displaystyle a_{n}=r^{n}} ? Substituting this guess (ansatz) in the recurrence relation, we find that
r n = A r n − 1 + B r n − 2 {\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}
must be true for all n > 1 {\displaystyle n>1} . Dividing through by r n − 2 {\displaystyle r^{n-2}} , we get that all these equations reduce to the same statement:
r 2 = A r + B , r 2 − A r − B = 0 , {\displaystyle {\begin{aligned}r^{2}&=Ar+B,\\r^{2}-Ar-B&=0,\end{aligned}}}
which is the characteristic equation of the recurrence relation. Solve for r {\displaystyle r} to obtain the two roots λ 1 {\displaystyle \lambda _{1}} , λ 2 {\displaystyle \lambda _{2}} : these roots are known as the characteristic roots or eigenvalues of the characteristic equation. The form of the solutions depends on the nature of these roots: If the roots are distinct, we have the general solution
a n = C λ 1 n + D λ 2 n {\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}
while if they are identical (when A 2 + 4 B = 0 {\displaystyle A^{2}+4B=0} ), we have
a n = C λ n + D n λ n {\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}}
This is the most general solution; the two constants C {\displaystyle C} and D {\displaystyle D} can be chosen based on two given initial conditions a 0 {\displaystyle a_{0}} and a 1 {\displaystyle a_{1}} to produce a specific solution. In the case of complex eigenvalues (which also gives rise to complex values for the solution parameters C {\displaystyle C} and D {\displaystyle D} ), the use of complex numbers can be eliminated by rewriting the solution in trigonometric form. In this case we can write the eigenvalues as λ 1 , λ 2 = α ± β i . {\displaystyle \lambda _{1},\lambda _{2}=\alpha \pm \beta i.} Then it can be shown that
a n = C λ 1 n + D λ 2 n {\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}
can be rewritten as
a n = 2 M n ( E cos ( θ n ) + F sin ( θ n ) ) = 2 G M n cos ( θ n − δ ) , {\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta ),}
where
M = α 2 + β 2 cos ( θ ) = α M sin ( θ ) = β M C , D = E ∓ F i G = E 2 + F 2 cos ( δ ) = E G sin ( δ ) = F G {\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}}
Here E {\displaystyle E} and F {\displaystyle F} (or equivalently, G {\displaystyle G} and δ {\displaystyle \delta } ) are real constants which depend on the initial conditions. Using
λ 1 + λ 2 = 2 α = A , {\displaystyle \lambda _{1}+\lambda _{2}=2\alpha =A,}
λ 1 ⋅ λ 2 = α 2 + β 2 = − B , {\displaystyle \lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,}
one may simplify the solution given above as
a n = ( − B ) n 2 ( E cos ( θ n ) + F sin ( θ n ) ) , {\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}
where a 1 {\displaystyle a_{1}} and a 2 {\displaystyle a_{2}} are the initial conditions and
E = − A a 1 + a 2 B F = − i A 2 a 1 − A a 2 + 2 a 1 B B A 2 + 4 B θ = arccos ( A 2 − B ) {\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}}
In this way there is no need to solve for λ 1 {\displaystyle \lambda _{1}} and λ 2 {\displaystyle \lambda _{2}} . In all cases—real distinct eigenvalues, real duplicated eigenvalues, and complex conjugate eigenvalues—the equation is stable (that is, the variable a {\displaystyle a} converges to a fixed value [specifically, zero]) if and only if both eigenvalues are smaller than one in absolute value. In this second-order case, this condition on the eigenvalues can be shown to be equivalent to | A | < 1 − B < 2 {\displaystyle |A|<1-B<2} , which is equivalent to | B | < 1 {\displaystyle |B|<1} and | A | < 1 − B {\displaystyle |A|<1-B} .
General solution
Characteristic polynomial and roots Solving the homogeneous equation
x t = a 1 x t − 1 + ⋯ + a n x t − n {\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}
involves first solving its characteristic polynomial
λ n = a 1 λ n − 1 + ⋯ + a n − 2 λ 2 + a n − 1 λ + a n {\displaystyle \lambda ^{n}=a_{1}\lambda ^{n-1}+\cdots +a_{n-2}\lambda ^{2}+a_{n-1}\lambda +a_{n}}
for its characteristic roots λ1, ..., λn. These roots can be solved for algebraically if n ≤ 4, but not necessarily otherwise. If the solution is to be used numerically, all the roots of this characteristic equation can be found by numerical methods. However, for use in a theoretical context it may be that the only information required about the roots is whether any of them are greater than or equal to 1 in absolute value. It may be that all the roots are real or instead there may be some that are complex numbers. In the latter case, all the complex roots come in complex conjugate pairs.
Solution with distinct characteristic roots If all the characteristic roots are distinct, the solution of the homogeneous linear recurrence
x t = a 1 x t − 1 + ⋯ + a n x t − n {\displaystyle x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}}
can be written in terms of the characteristic roots as
x t = c 1 λ 1 t + ⋯ + c n λ n t {\displaystyle x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}}
where the coefficients ci can be found by invoking the initial conditions. Specifically, for each time period for which an iterate value is known, this value and its corresponding value of t can be substituted into the solution equation to obtain a linear equation in the n as-yet-unknown parameters; n such equations, one for each initial condition, can be solved simultaneously for the n parameter values. If all characteristic roots are real, then all the coefficient values ci will also be real; but with non-real complex roots, in general some of these coefficients will also be non-real.
Converting complex solution to trigonometric form If there are complex roots, they come in conjugate pairs and so do the complex terms in the solution equation. If two of these complex terms are cjλtj and cj+1λtj+1, the roots λj can be written as
λ j , λ j + 1 = α ± β i = M ( α M ± β M i ) {\displaystyle \lambda _{j},\lambda _{j+1}=\alpha \pm \beta i=M\left({\frac {\alpha }{M}}\pm {\frac {\beta }{M}}i\right)}
where i is the imaginary unit and M is the modulus of the roots:
M = α 2 + β 2 . {\displaystyle M={\sqrt {\alpha ^{2}+\beta ^{2}}}.}
Then the two complex terms in the solution equation can be written as
c j λ j t + c j + 1 λ j + 1 t = M t ( c j ( α M + β M i ) t + c j + 1 ( α M − β M i ) t ) = M t ( c j ( cos θ + i sin θ ) t + c j + 1 ( cos θ − i sin θ ) t )