Skip to content

27. Applications to Difference Equations

Dated: 11-06-2025

Discrete time Signals

Let \(S\) be a space of discrete time signals and \(s \in S\) be a function1 defined over integers and is visualized by a sequence2 \(\{y_k\}\).

Example

The crystal clear sounds from a compact disc player are produced from music that has been sampled at the rate of \(41,000\) times per second. At each measurement, the amplitude of the music signal is recorded as a number, say, \(y_k\). The original music is composed of many different sounds of varying frequencies, yet the sequence2 \(\{y_k\}\) contains enough information to reproduce all the frequencies in the sound up to about \(20,000\) cycles per second, higher than the human ear can sense.

Linear Independence in the space \(S\) of Signals

Consider 3 signals \(\{\vec u_k\}, \{\vec v_k\}\) and \(\{\vec w_k\}\) and they are linearly independent when

\[c_1 \vec u_k + c_2 \vec v_k + c_3 \vec w_k = 0 \quad \forall k\]

For the next 2 consecutive samples,

\[c_1 \vec u_{k + 1} + c_2 \vec v_{k + 1} + c_3 \vec w_{k + 1} = 0 \quad \forall k\]
\[c_1 \vec u_{k + 2} + c_2 \vec v_{k + 2} + c_3 \vec w_{k + 2} = 0 \quad \forall k\]
\[ \implies \begin{bmatrix} \vec u_k & \vec v_k & \vec w_k \\ \vec u_{k + 1} & \vec v_{k + 1} & \vec w_{k + 1} \\ \vec u_{k + 2} & \vec v_{k + 2} & \vec w_{k + 2} \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \end{bmatrix} \]

The coefficient matrix3 in this system is called thee Casorati matrix of the signals and its determinant is called the Casoratian.

Linear Difference Equations

Given scalars \(a_0, \ldots, a_n \neq 0\) and a signal \(\{z_k\}\), the following equation is called linear difference equation or linear recurrence relation of order \(n\).

\[a_0 \cdot \vec y_{k + n} + a_1 \cdot \vec y_{k + n - 1} + \ldots + a_{n - 1} \cdot \vec y_{k + 1} + a_n \cdot \vec y_k = \vec z_k\]

In simple words, an equation which expresses a value of a sequence2 as a function of the other terms in the sequence2 is called a difference equation.

Example

In digital signal processing, an equation like above describes a linear filter and the coefficients \(a_0, \ldots, a_n\) are called the filter coefficients.
If \(\{y_k\}\) is treated as the input and \(\{z_k\}\) the output, then the solutions of the associated homogeneous equation are the signals that are filtered out and transformed into the zero signal.

Assume a filter

\[0.35 \vec y_{k + 2} + 0.5 \vec y_{k+1} + 0.35 \vec y_k = \vec z_k\]

Signal 1

\[\vec y = \cos\left(\frac {\pi t} 4\right)\]

If we sample this for integer values of \(t\), we get

\[\{\vec y_k\} = \left\{\cos(0), \cos\left(\frac \pi 4\right), \cos\left(\frac {2 \pi} 4\right), \ldots\right\}\]
\[= \{1, 0.7, 0, -0.7, \ldots\}\]
\(k\) \(\vec y_k\) \(\vec y_{k + 1}\) \(\vec y_{k + 2}\) \(0.35 \vec y_{k + 2} + 0.5 \vec y_{k+1} + 0.35 \vec y_k = \vec z_k\)
\(0\) \(1\) \(0.7\) \(0\) \(0.7\)
\(1\) \(0.7\) \(0\) \(-0.7\) \(0\)
\(2\) \(0\) \(-0.7\) \(-1\) \(-0.7\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)

Signal 2

\[\vec y = \cos\left(\frac{3 \pi t} 4\right)\]
\[\{\vec w_k\} = \{1, -0.7, 0, 0.7, \ldots\}\]

After this signal is passed through the filter, the output it zero sequence.
This filter is called the low pass filter as it allows a signal of lower frequency \(\{\vec y_k\}\) but blocks \(\{\vec w_k\}\).

Example

\[y_{k + 3} - 2y_{k + 2} - 5y_{k + 1} + 6 y_k = 0 \quad \forall k\]

Substitute \(r^k = y_k\)

\[r^{k+3} - 2r^{k+2} - 5r^{k+1} + 6r^k = 0\]
\[r^k (r^3 - 2r^2 - 5r + 6) = 0\]

Using synthetic division

\[ \begin{array}{c|ccc|c} & 1 & -2 & -5 & 6 \\ 1 & 0 & 1 & -1 & -6 \\ \hline & 1 & -1 & -6 & 0 \end{array} \]
\[r^k ((x-1)(x^2 - x - 6)) = 0\]

\(\(r^k ((x-1)(x^2 - 3x + 2x - 6)) = 0\)\)

\(\(r^k ((x-1) (x(x-3)+2(x-3))) = 0\)\)

\(\(r^k (r-1)(r+2)(r-3) = 0\)\)

\[r - 1 = 0 \implies r = 1\]
\[r + 2 = 0 \implies r = -2\]
\[r - 3 = 0 \implies r = 3\]
\[r^k = 0 \implies 1^k, (-2)^k, 3^k \text{ are the solutions}\]

If \(r\) is a root of auxiliary equation

\[r^n + a_1 \cdot r^{n-1} + \ldots + a_{n-1} \cdot r + a_n \cdot 1 = 0\]

then a non zero signal \(r^k\) satisfies the homogeneous difference equation

\[y_{k+n} + a_1 y_{k+n-1} + \dots + a_{n-1} y_{k+1} + a_n y_k = 0 \quad \forall k\]

Solution Sets of Linear Difference Equations

Given \(a_1, \ldots, a_n\), consider mapping \(T: \mathbb S \to \mathbb S\) that transforms a signal \(\{y_k\}\) to \(\{w_k\}\) given by

\[w_k = y_{k+n} + a_1 y_{k+n-1} + \ldots + a_{n-1} y_{k+1} + a_n y_k\]

Since \(T\) is a linear transformation,4 this implies that the solution to homogeneous equation

\[y_{k+n} + a_1 y_{k+n-1} + \dots + a_{n-1} y_{k+1} + a_n y_k = 0\]

is the kernel5 of \(T\) (since it is set6 of signals which map to zero signal) and hence, is a solution of subspace7 of \(S\).

Theorem

If \(a_n \neq 0\) and if \(\{z_k\}\) is given by

\[y_{k+n} + a_1 y_{k+n-1} + \dots + a_{n-1} y_{k+1} + a_n y_k = 0 \quad \forall k\]

has a unique solution whenever \(y_0, \ldots, y_{n - 1}\) are specified.

Theorem

The set6 \(\mathbb H\) of all solutions of the \(n^{th}\) order homogeneous linear difference equation

\[y_{k+n} + a_1 y_{k+n-1} + \dots + a_{n-1} y_{k+1} + a_n y_k = 0 \quad \forall k\]

is an \(n\) dimensional vector space.7

Non-homogeneous Equations

The solution for the following

\[y_{k+n} + a_1 y_{k+n-1} + \dots + a_{n-1} y_{k+1} + a_n y_k = 0 \quad \forall k\]

has the form

\[s = p + h\]

where \(s\) is the solution, \(p\) is the particular solution and \(h\) is the linear combination4 of a fundamental set6 of solutions for the corresponding homogeneous equation.

Reduction to Systems of First-order Equations

A modern way to study a homogeneous \(n^{th}\) order linear difference equation is to replace it by an equivalent system of first order difference equations, written in the form \(\vec x_{k+1} = A_{n \times n} \vec x_k\) where \(\vec x \in \mathbb R^n\).

Example

Write the following difference equation as a first order system

\[y_{k+3} - 2y_{k+2} - 5y_{k+1} + 6y_k = 0 \quad \forall k\]

Solution

For each \(k\),

\[x_k = \begin{bmatrix} y_k \\ y_{k+1} \\ y_{k+2} \end{bmatrix}\]
\[\because y_{k+3} - 2y_{k+2} - 5y_{k+1} + 6y_k = 0\]
\[\implies y_{k+3} = 2y_{k+2} + 5y_{k+1} - 6y_k\]
\[ x_{k+1} = \begin{bmatrix} y_{k+1} \\ y_{k+2} \\ y_{k+3} \end{bmatrix} = \begin{bmatrix} 0 + y_{k+1} + 0 \\ 0 + 0 + y_{k+2} \\ -6y_k + 5y_{k+1} + 2y_{k+2} \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -6 & 5 & 2 \end{bmatrix} \begin{bmatrix} y_k \\ y_{k+1} \\ y_{k+2} \end{bmatrix} \]
\[\vec x_{k + 1} = A \vec x_k \quad \forall k\]

Where

\[A=\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ -6 & 5 & 2 \end{bmatrix}\]

In general

\[ x_k = \begin{bmatrix} y_k \\ y_{k+1} \\ \vdots \\ y_{k+n-1} \end{bmatrix}, \quad A = \begin{bmatrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ -a_n & -a_{n-1} & -a_{n-2} & \dots & -a_1 \end{bmatrix}\]

References

Read more about notations and symbols.

  1. Read more about functions. ↩

  2. Read more about sequences. ↩↩↩↩

  3. Read more about coefficient matrices. ↩

  4. Read more about linear transformations. ↩↩

  5. Read more about kernels. ↩

  6. Read more about sets. ↩↩↩

  7. Read more about vector spaces. ↩↩