4.8 Applications to difference equations

Big idea

A linear difference equation says each term of a sequence is a fixed combination of the terms just before it. Population counts, loan balances and sampled filter outputs all obey rules of that shape. Collect every sequence obeying one such rule and you get a set closed under addition and scaling: a vector space of solutions.

That observation converts a question about sequences into the questions of this chapter. The solution space of a rule of order $n$ has dimension $n$, so finding $n$ independent solutions gives you all of them: every solution is a combination of those, and the weights are fixed by the starting values. Guess-and-check is enough, provided you check independence.

There is a second reading that ties the rule to matrices. Bundle $n$ consecutive terms into a vector and the rule becomes a single matrix acting on that bundle, advancing it one step. Advancing $k$ steps is then a matrix power, and the long-run behaviour of the sequence becomes a question about powers of a fixed matrix.

Decoder

The set of all solutions of a homogeneous linear difference equation of order $n$ is an $n$-dimensional vector space of signals.

“Homogeneous” means the right-hand side is zero, with no forcing term added on. “Order $n$” means the rule reaches back $n$ steps, so $n$ starting values are needed before the sequence can run.

The dimension claim is where the work saved comes from. It says: hunt down $n$ solutions, prove they are independent, and stop. Nothing else exists, so any solution someone else produces is already a combination of yours. The $n$ is the same $n$ as the number of starting values, which is the intuitive reason the two match.

Definitions and results

Linear difference equation. A homogeneous linear difference equation of order $n$ with constant coefficients has the form

$$ y_{k+n} + a_{n-1}y_{k+n-1} + \cdots + a_1 y_{k+1} + a_0 y_k = 0 $$

for all $k$, with $a_0 \ne 0$. A solution is a signal whose samples satisfy the rule at every index.

The solution set is a subspace. If two signals satisfy the rule, so does their sum, since each term of the rule adds; so does any scalar multiple, since each term scales. The zero signal satisfies it. So the solutions form a subspace of the space of all signals.

Dimension of the solution space. The solution space of an order-$n$ equation has dimension $n$. Specifying the first $n$ terms determines the rest, and the map sending a solution to its first $n$ terms is linear, one-to-one and onto $\mathbb{R}^n$. So a basis of $n$ solutions describes every solution.

Characteristic equation. Try $y_k = r^k$ with $r \ne 0$. Substituting and dividing by $r^k$ leaves

$$ r^n + a_{n-1}r^{n-1} + \cdots + a_1 r + a_0 = 0 $$

Each root $r$ gives the solution $\{r^k\}$. Distinct real roots give distinct solutions, and $n$ of them form a basis.

Repeated roots. If $r$ is a root repeated $m$ times, then $\{r^k\}$, $\{k r^k\}$, up to $\{k^{m-1}r^k\}$ are all solutions, and together with the solutions from the other roots they still give $n$ independent signals.

Testing independence of solutions. Sample each candidate solution at $n$ consecutive indices and put the samples in an $n \times n$ matrix, one solution per column. If that matrix is invertible, the solutions are independent. This works because a dependence relation among signals forces the same relation among their sampled columns, and conversely a solution is pinned down by $n$ consecutive samples.

Fitting the starting values. With a basis $\{u_k\}, \dots$ in hand, the general solution is a combination with unknown weights. Substituting the given starting values produces a square system in those weights, and the same invertible matrix from the independence test solves it.

Matrix form. Set $\mathbf{x}_k = (y_k, y_{k+1}, \dots, y_{k+n-1})$. The rule says $\mathbf{x}_{k+1} = A\mathbf{x}_k$ for a fixed $n \times n$ matrix whose last row holds the negated coefficients and whose other rows shift the entries up. Iterating gives

$$ \mathbf{x}_k = A^k \mathbf{x}_0 $$

so every term of the sequence is read off a power of one matrix applied to the vector of starting values.

Nonhomogeneous equations. If the right-hand side is a nonzero signal, the solution set is no longer a subspace. It is one particular solution plus the whole solution space of the matching homogeneous equation, the same structure as for $A\mathbf{x} = \mathbf{b}$ against $A\mathbf{x} = \mathbf{0}$.

Worked examples

Solving a second-order rule

Take $y_{k+2} = y_{k+1} + 2y_k$, with $y_0 = 1$ and $y_1 = 8$. Written homogeneously it is $y_{k+2} - y_{k+1} - 2y_k = 0$, so the characteristic equation is

$$ r^2 - r - 2 = 0 $$

which factors as $(r - 2)(r + 1) = 0$, giving roots $r = 2$ and $r = -1$. So $\{2^k\}$ and $\{(-1)^k\}$ are solutions.

Check independence by sampling at $k = 0$ and $k = 1$. The columns are $(1, 2)$ and $(1, -1)$, and

$$ \det\begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix} = -1 - 2 = -3 $$

which is not zero. Two independent solutions in a two-dimensional solution space make a basis, so every solution has the form $y_k = c_1 2^k + c_2(-1)^k$.

Fit the starting values: $c_1 + c_2 = 1$ and $2c_1 - c_2 = 8$. Adding gives $3c_1 = 9$, so $c_1 = 3$ and $c_2 = -2$. The answer is

$$ y_k = 3 \cdot 2^k - 2(-1)^k $$

Check it against the rule directly. The formula gives $y_0 = 3 - 2 = 1$ and $y_1 = 6 + 2 = 8$, matching the starting values. It gives $y_2 = 12 - 2 = 10$, and the rule predicts $y_1 + 2y_0 = 8 + 2 = 10$. It gives $y_3 = 24 + 2 = 26$, and the rule predicts $y_2 + 2y_1 = 10 + 16 = 26$. Both agree.

The same rule as a matrix power

Bundle two consecutive terms: $\mathbf{x}_k = (y_k, y_{k+1})$. The rule says the next bundle is $(y_{k+1},\; 2y_k + y_{k+1})$, so

$$ A = \begin{bmatrix} 0 & 1 \\ 2 & 1 \end{bmatrix}, \qquad \mathbf{x}_0 = \begin{bmatrix} 1 \\ 8 \end{bmatrix} $$

Advance one step: $A\mathbf{x}_0 = (8,\; 2 + 8) = (8, 10)$, which is $(y_1, y_2)$, matching $y_2 = 10$ from before.

Jump three steps with a power instead. First

$$ A^2 = \begin{bmatrix} 0 & 1 \\ 2 & 1 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 2 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 2 & 3 \end{bmatrix}, \qquad A^3 = \begin{bmatrix} 2 & 1 \\ 2 & 3 \end{bmatrix}\begin{bmatrix} 0 & 1 \\ 2 & 1 \end{bmatrix} = \begin{bmatrix} 2 & 3 \\ 6 & 5 \end{bmatrix} $$

Then $A^3\mathbf{x}_0 = (2 + 24,\; 6 + 40) = (26, 46)$, which claims $y_3 = 26$ and $y_4 = 46$.

Check both. The closed formula gives $y_3 = 3 \cdot 8 + 2 = 26$ and $y_4 = 3 \cdot 16 - 2 = 46$. The rule gives $y_4 = y_3 + 2y_2 = 26 + 20 = 46$. All three routes agree.

Notice the roots of the characteristic equation, $2$ and $-1$, showing up again: they are the numbers whose powers drive $A^k$, which is the link this construction sets up for the next chapter.

A repeated root

Take $y_{k+2} - 6y_{k+1} + 9y_k = 0$. The characteristic equation is $r^2 - 6r + 9 = 0$, which is $(r - 3)^2 = 0$, so $3$ is a root twice and $\{3^k\}$ is only one solution. The solution space still has dimension two, so one more independent solution exists.

Try $\{k\,3^k\}$. Substituting gives

$$ (k+2)3^{k+2} - 6(k+1)3^{k+1} + 9k\,3^k = 3^k\left[9(k+2) - 18(k+1) + 9k\right] $$

The bracket is $9k + 18 - 18k - 18 + 9k = 0$, so the signal satisfies the rule at every $k$ and is a solution.

Check independence by sampling at $k = 0$ and $k = 1$. The columns are $(1, 3)$ and $(0, 3)$, and

$$ \det\begin{bmatrix} 1 & 0 \\ 3 & 3 \end{bmatrix} = 3 $$

which is not zero, so the two are independent and form a basis. Every solution is $y_k = c_1 3^k + c_2 k\,3^k$.

Check one case numerically. Starting from $y_0 = 1$, $y_1 = 3$, the weights solve $c_1 = 1$ and $3c_1 + 3c_2 = 3$, so $c_2 = 0$ and $y_k = 3^k$. The rule then predicts $y_2 = 6(3) - 9(1) = 9$, and $3^2 = 9$. Starting instead from $y_0 = 0$, $y_1 = 3$ gives $c_1 = 0$ and $c_2 = 1$, so $y_2$ should be $2 \cdot 9 = 18$; the rule gives $6(3) - 9(0) = 18$. Both match.

Practice

First the independence test on candidate solutions, sampled into columns and checked with a determinant.

Then the matrix form: advance a bundled state with powers of the coefficient matrix.

Quiz

Five items on solution spaces of difference equations, independence of solutions, and the matrix-power form.