0% Complete
0/19 Steps

Linear recurrences

Linear difference equations

Definition
linear difference equation is a recurrence relation of the form y_{t+n}=a_1y_{t+n-1}+a_2y_{t+n-2}+\cdots +a_ny_t+b. If b=0, then it is called homogeneous. In this article, we shall also assume t=0 for convenience. The name “difference equation” is a nod to the fact that it is analogous to a differential equation if we take finite differences instead of taking limits. (Note that, \frac{dy}{dx}=\lim_{h\to 0}\frac{y(x+h)-y(x)}{h}=\lim_{\Delta x\to 0}\frac{\Delta y}{\Delta x}.) In what follows, we shall illustrate a common method to explicitly solve such equations.

 

The solution space
Note that, if two sequences z_n and w_n are solutions to the given equation (in the homogeneous case), then az_n+bw_n is also a solution for any two constants a,b. In such cases, the set of all solutions is said to possess a linear structure. It means that the solutions can be thought of as vectors in an abstract space (more on this later). If this space is simply \mathbb{R}^2 or \mathbb{R}^3, then we can use our knowledge of vectors in these spaces to find all solutions in terms of a few special ones.

A useful example
Consider the equation y_n=py_{n-1}+qy_{n-2}. Note that, given y_0 and y_1, y_n is determined for all n\ge 2. Thus, there exists a one-to-one correspondence between the set of all solutions (let us call it \Gamma) and the set of all (y_0,y_1) (the latter is just \mathbb{R}^2). Hence, \Gamma is nothing but \mathbb{R}^2 (in linear algebra, this correspondence is called a linear isomorphism). Note that, given two non-colinear vectors in the plane, any third vector can be written as a linear combination of the first two (please check!). Thus, given the solutions corresponding to two such vectors, any other solution can be written as a linear combination of them.
The method
Let us look for solutions of the form y_n=\lambda^n. Plugging into the equation, we get \lambda^2-p\lambda-q=0 (this is called the characteristic equation of the recurrence). Solving, we get two values \lambda_+ and \lambda_-. If they are different, then the corresponding vectors in \mathbb{R}^2 are not colinear (check!). Hence, given any solution x_n there exist a,b such that x_n=a\lambda_+^n+b\lambda_-^n. If the roots are the same, then the x_n maybe written in the form (a+bn)\lambda^n (why?)

Comments

The above method generalises to difference equations with solution spaces of dimension higher than 2 if the roots of the characteristic equation are all distinct. However, the trick used to deal with coincident roots in the example does not generalise immediately to higher dimensions.

 The non-homogeneous case can be transformed into the homogeneous case by making a linear change of variables. See more on this here.

Follow Along

Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Sed molestie, velit ut eleifend sollicitudin, neque orci tempor nulla, id sagittis nisi ante nec arcu.

Free Courses

Duis egestas aliquet aliquet. Maecenas erat eros, fringilla et leo eget, viverra pretium nulla. Quisque sed augue tincidunt, posuere dui tempor.

Premium Courses

Duis egestas aliquet aliquet. Maecenas erat eros, fringilla et leo eget, viverra pretium nulla. Quisque sed augue tincidunt, posuere dui tempor.

Ready to get started?

Get in touch, or create an account