How to Solve Difference Equations: Video Tutorial

Difference equations, also known as recurrence relations, are similar to differential equations. The difference is that they are defined in discrete domains, such as discrete time or space. They describe a sequence $x_n$ in which each term depends on the terms before it.

This video tutorial presents the general form of linear difference equations and recurrence relations. It explains a solution approach based on eigenfunctions and eigenvalues. Several examples are worked out, including the Fibonacci series. The tutorial also covers the case of repeated (non-distinct) roots of the characteristic equation. Finally, it discusses non-homogeneous difference equations through the concepts of general and particular solutions.

Mostapha Kalami Heris teaches the 35 minute 59 second video. Follow the worked recurrences to see how initial conditions determine the constants in each solution.

A first example

The video starts with the simple equation $x_n = x_{n-1} + 1$. Its solution is $x_n = n + c$, where the constant $c$ comes from the initial condition. With $x_0 = 0$ the sequence is $0, 1, 2, 3, \dots$, and with $x_0 = 2$ it is the same sequence shifted by two. As with differential equations, the equation gives the structure of the solution, and the initial values select one solution.

The characteristic equation method

Consider the second order linear equation

with given values of $x_0$ and $x_1$. The key idea is that $s^n$ plays the same role for differences as $e^{st}$ plays for derivatives. If $x_n = \alpha x_{n-1}$, then trying $x_n = s^n$ gives $s^n = \alpha s^{n-1}$, so $s = \alpha$ and the solution is $\alpha^n$. In this sense, $s^n$ is an eigenfunction of the shift (time delay) operation.

For the second order equation, the same trial solution gives the characteristic equation:

If its roots $s_1$ and $s_2$ are distinct, the general solution is a linear combination of the two eigenfunctions:

The constants $c_1$ and $c_2$ come from the initial conditions. The same method works for any order $k$: the characteristic equation has degree $k$, and its $k$ roots give the terms of the solution.

Worked example: the Fibonacci sequence

The Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$ and $F_n = F_{n-1} + F_{n-2}$, which gives $0, 1, 1, 2, 3, 5, 8, 13, 21, \dots$. The characteristic equation is $s^2 = s + 1$, and its roots are

The initial conditions give two linear equations, $c_1 + c_2 = 0$ and $c_1 s_1 + c_2 s_2 = 1$. Their solution is $c_1 = 1/\sqrt{5}$ and $c_2 = -1/\sqrt{5}$, so

This closed form is known as Binet’s formula. The video checks it in MATLAB (from 10:40): it finds the roots of the characteristic polynomial with roots, defines the formula as a function of $n$, and computes the first terms of the sequence.

The closed form also proves a well known fact. Since $|s_2| < 1$, the second term vanishes as $n$ grows, so the ratio $F_n / F_{n-1}$ tends to $s_1$, the golden ratio $(1 + \sqrt{5})/2$.

Repeated roots

When the characteristic equation has a repeated root, the formula above does not give enough independent terms. The video uses the example $x_n = 2x_{n-1} - x_{n-2}$ (from 18:18). Its characteristic equation $s^2 - 2s + 1 = 0$ has the double root $s = 1$. As in differential equations, the second term is multiplied by $n$:

With $x_0 = 1$ and $x_1 = 2$, this gives $c_1 = c_2 = 1$ and $x_n = 1 + n$. For a root repeated three times, the terms are multiplied by $1$, $n$ and $n^2$, and so on.

Non-homogeneous equations

When the equation has a term that does not contain $x$, such as $x_n = 2x_{n-1} + n$, the solution has two parts (from 20:58):

The general solution $x_n^{(g)}$ solves the homogeneous equation, here $c \cdot 2^n$. The particular solution $x_n^{(p)}$ is any one solution of the full equation. For the polynomial forcing in this example, the video tries $\alpha n^2 + \beta n + \gamma$ and matches the coefficients of both sides. This gives $\alpha = 0$, $\beta = -1$ and $\gamma = -2$, so $x_n^{(p)} = -n - 2$. With $x_0 = 1$, the full solution is

The video starts with a polynomial of higher degree than needed on purpose. A trial polynomial that is too low in degree can lead to inconsistent coefficient equations. If the trial overlaps a homogeneous solution, multiply it by a suitable power of $n$ before matching coefficients. Extra terms are harmless in this example, but a trial form must still account for repeated roots and overlap.

A final example with both cases

The last example (from 28:47) combines a repeated root with a non-homogeneous term:

The characteristic equation $s^2 - 4s + 4 = 0$ has the double root $s = 2$, so the general solution is $c_1 2^n + c_2\, n\, 2^n$. The trial $\alpha n + \beta$ gives the particular solution $n + 5$. With $x_0 = 0$ and $x_1 = 5$, the constants are $c_1 = -5$ and $c_2 = 9/2$, and the solution is

Where difference equations are used

Difference equations appear wherever a quantity is updated in discrete steps: digital signal processing and digital control, the analysis of recursive algorithms in computer science, discrete time models in economics and population models.

Who this tutorial is for

• Math students
• Computer science students
• Engineering students
• Anyone interested in mathematics

The tutorial needs only basic mathematics.

Check a closed form

Verify the initial conditions first, then substitute the expression into the recurrence. For the Fibonacci example, compute several small integer terms and compare them with direct iteration. Binet’s formula is exact symbolically, but powers and subtraction in floating point arithmetic can lose accuracy for large indices.

Watch online

The video tutorial is available to watch online on the Yarpiz YouTube channel.

Play videoLoads from YouTube

Mostapha Kalami Heris, How to Solve Difference Equations: Video Tutorial (YPTDEQ190520), Yarpiz, 2019. https://yarpiz.com/how-to-solve-difference-equations-yptdeq190520

@misc{yarpiz-yptdeq190520,
  author = {{Mostapha Kalami Heris}},
  title = {{How to Solve Difference Equations: Video Tutorial}},
  howpublished = {Yarpiz},
  year = {2019},
  note = {Code YPTDEQ190520},
  url = {https://yarpiz.com/how-to-solve-difference-equations-yptdeq190520}
}