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 , one period earlier denoted as , one period later as , etc.
The solution of such an equation is a function of , 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 of the iterates, and normally these are the 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 and :
or equivalently as
The positive integer is called the order of the recurrence and denotes the longest time lag between iterates. The equation is called homogeneous if and nonhomogeneous if .
If the equation is homogeneous, the coefficients determine the characteristic polynomial (also "auxiliary polynomial" or "companion polynomial")
whose roots play a crucial role in finding and understanding the sequences satisfying the recurrence.
Conversion to homogeneous form
If , the equation
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 such that, if successive iterates all had this value, so would all future values. This value is found by setting all values of equal to in the difference equation, and solving, thus obtaining
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
which has no constant term, and which can be written more succinctly as
where equals . This is the homogeneous form.
If there is no steady state, the difference equation
can be combined with its equivalent form
to obtain (by solving both for )
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 distinct roots then each solution to the recurrence takes the form
where the coefficients 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 . For instance, if the characteristic polynomial can be factored as , with the same root occurring three times, then the solution would take the form
Order 1
For order 1, the recurrence
has the solution with and the most general solution is with . The characteristic polynomial equated to zero (the characteristic equation) is simply .
Order 2
Solutions to such recurrence relations of higher order are found by systematic means, often using the fact that is a solution for the recurrence exactly when is a root of the characteristic polynomial. This can be approached directly or using generating functions (formal power series) or matrices.
