Linear recurrence with constant coefficients

In mathematics and in particular dynamical systems, a linear difference equation^[1]^{: ch. 17}^[2]^{: ch. 10} or linear recurrence relation 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. Usually the context is 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.

An $n$ th order linear difference equation is one that can be written in terms of parameters $a i$ and $b$ as

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}+\cdots +a_{n}y_{t}+b

The equation is called homogeneous if $b = 0$ and nonhomogeneous if $b \neq 0$ . Since the longest time lag between iterates appearing in the equation is $n$ , this is an $n$ th order equation, where $n$ could be any positive integer. When the longest lag is specified numerically so $n$ does not appear notationally as the longest time lag, $n$ is occasionally used instead of $t$ to index iterates.

In the most general case the coefficients $a i$ and $b$ could themselves be functions of time; however, this article treats the most common case, that of constant coefficients. If the coefficients $a i$ are polynomials in $t$ the equation is called a linear recurrence equation with polynomial coefficients.

The solution of such an equation is a function of time, 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.

Solution of homogeneous case

Characteristic equation and roots

Solving the homogeneous equation

x_{t}=a_{1}x_{t-1}+\cdots +a_{n}x_{t-n}

involves first solving its characteristic equation

\lambda ^{n}=a_{1}\lambda ^{n-1}+\cdots +a_{n-2}\lambda ^{2}+a_{n-1}\lambda +a_{n}

for its characteristic roots $λ i$ ( $i = 1, ..., n$ ). These roots can be solved for algebraically if $n \leq 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 no characteristic roots share the same value, the solution of the homogeneous linear difference equation

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}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}

where the coefficients $c i$ 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 $c i$ 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 pairs and so do the complex terms in the solution equation. If two of these complex terms are $c j λ t j$ and $c j +1 λ t j +1$ , the roots $λ j$ can be written as

\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={\sqrt {\alpha ^{2}+\beta ^{2}}}

Then the two complex terms in the solution equation can be written as

{\begin{aligned}c_{j}\lambda _{j}^{t}+c_{j+1}\lambda _{j+1}^{t}&=M^{t}\left(c_{j}\left({\frac {\alpha }{M}}+{\frac {\beta }{M}}i\right)^{t}+c_{j+1}\left({\frac {\alpha }{M}}-{\frac {\beta }{M}}i\right)^{t}\right)\\[6pt]&=M^{t}\left(c_{j}\left(\cos \theta +i\sin \theta \right)^{t}+c_{j+1}\left(\cos \theta -i\sin \theta \right)^{t}\right)\\[6pt]&=M^{t}{\bigl (}c_{j}\left(\cos \theta t+i\sin \theta t\right)+c_{j+1}\left(\cos \theta t-i\sin \theta t\right){\bigr )}\end{aligned}}

where $θ$ is the angle whose cosine is $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠α/M⁠$ and whose sine is $⁠ β / M ⁠$ ; the last equality here made use of de Moivre's formula.

Now the process of finding the coefficients $c j$ and $c j +1$ guarantees that they are also complex conjugates, which can be written as $γ \pm δi$ . Using this in the last equation gives this expression for the two complex terms in the solution equation:

2M^{t}\left(\gamma \cos \theta t-\delta \sin \theta t\right)

which can also be written as

2{\sqrt {\gamma ^{2}+\delta ^{2}}}M^{t}\cos(\theta t+\psi )

where $ψ$ is the angle whose cosine is $⁠ γ / \sqrt γ 2 + δ 2 ⁠$ and whose sine is $⁠ δ / \sqrt γ 2 + δ 2 ⁠$ .

Cyclicity

Depending on the initial conditions, even with all roots real the iterates can experience a transitory tendency to go above and below the steady state value. But true cyclicity involves a permanent tendency to fluctuate, and this occurs if there is at least one pair of complex conjugate characteristic roots. This can be seen in the trigonometric form of their contribution to the solution equation, involving $cos θt$ and $sin θt$ .

Solution with duplicate characteristic roots

In the second-order case, if the two roots are identical ( $λ 1 = λ 2$ ), they can both be denoted as $λ$ and a solution may be of the form

x_{t}=c_{1}\lambda ^{t}+c_{2}t\lambda ^{t}

Conversion to homogeneous form

If $b \neq 0$ , the equation

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^{*}={\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

\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}+\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}+\cdots +a_{n}y_{t-n}+b

can be combined with its equivalent form

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}-\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.

Stability

In the solution equation

x_{t}=c_{1}\lambda _{1}^{t}+\cdots +c_{n}\lambda _{n}^{t}

a term with real characteristic roots converges to 0 as $t$ grows indefinitely large if the absolute value of the characteristic root is less than 1. If the absolute value equals 1, the term will stay constant as $t$ grows if the root is +1 but will fluctuate between two values if the root is −1. If the absolute value of the root is greater than 1 the term will become larger and larger over time. A pair of terms with complex conjugate characteristic roots will converge to 0 with dampening fluctuations if the absolute value of the modulus $M$ of the roots is less than 1; if the modulus equals 1 then constant amplitude fluctuations in the combined terms will persist; and if the modulus is greater than 1, the combined terms will show fluctuations of ever-increasing magnitude.

Thus the evolving variable $x$ will converge to 0 if all of the characteristic roots have magnitude less than 1.

If the largest root has absolute value 1, neither convergence to 0 nor divergence to infinity will occur. If all roots with magnitude 1 are real and positive, $x$ will converge to the sum of their constant terms $c i$ ; unlike in the stable case, this converged value depends on the initial conditions: different starting points lead to different points in the long run. If any root is −1, its term will contribute permanent fluctuations between two values. If any of the unit-magnitude roots are complex then constant-amplitude fluctuations of $x$ will persist.

Finally, if any characteristic root has magnitude greater than 1, then $x$ will diverge to infinity as time goes to infinity, or will fluctuate between increasingly large positive and negative values.

A theorem of Issai Schur states that all roots have magnitude less than 1 (the stable case) if and only if a particular string of determinants are all positive.^[2]^: 247

If a non-homogeneous linear difference equation has been converted to homogeneous form which has been analyzed as above, then the stability and cyclicality properties of the original non-homogeneous equation will be the same as those of the derived homogeneous form, with convergence in the stable case being to the steady-state value $y *$ instead of to 0.

Solution by conversion to matrix form

An alternative solution method involves converting the $n$ th order difference equation to a first-order matrix difference equation. This is accomplished by writing $w 1, t = y t$ , $w 2, t = y t -1 = w 1, t -1$ , $w 3, t = y t -2 = w 2, t -1$ , and so on. Then the original single $n$ th-order equation

y_{t}=a_{1}y_{t-1}+a_{2}y_{t-2}+\cdots +a_{n}y_{t-n}+b

can be replaced by this set of $n$ first-order equations:

{\begin{aligned}w_{1,t}&=a_{1}w_{1,t-1}+a_{2}w_{2,t-1}+\cdots +a_{n}w_{n,t-1}+b\\w_{2,t}&=w_{1,t-1}\\&\,\,\,\vdots \\w_{n,t}&=w_{n-1,t-1}.\end{aligned}}

Defining the vector $w i$ as

\mathbf {w} _{i}={\begin{bmatrix}w_{1,i}\\w_{2,i}\\\vdots \\w_{n,i}\end{bmatrix}}

this can be put in matrix form as

\mathbf {w} _{t}=\mathbf {A} \mathbf {w} _{t-1}+\mathbf {b}

Here $A$ is an $n \times n$ matrix in which the first row contains $a 1, ..., a n$ and all other rows have a single 1 with all other elements being 0, and $b$ is a column vector with first element $b$ and with the rest of its elements being 0.

This matrix equation can be solved using the methods in the article Matrix difference equation.

References

^ Chiang, Alpha (1984). Fundamental Methods of Mathematical Economics (Third ed.). New York: McGraw-Hill. ISBN 0-07-010813-7.
^ ^a ^b Baumol, William (1970). Economic Dynamics (Third ed.). New York: Macmillan. ISBN 0-02-306660-1.

[Chiang-1] Chiang, Alpha (1984). Fundamental Methods of Mathematical Economics (Third ed.). New York: McGraw-Hill. ISBN 0-07-010813-7.

[Baumol-2] Baumol, William (1970). Economic Dynamics (Third ed.). New York: Macmillan. ISBN 0-02-306660-1.

[1]

[2]