Homogeneous Linear Difference Equations: General Solutions

Hello! Welcome to the first lesson in our course.

Our goal is to develop a foundational understanding of the key mathematical concepts used in the paper you're interested in. This first lesson focuses on the bedrock of the entire paper: homogeneous linear difference equations.

The paper's central problem is to maximize the amplitude of solutions to these equations. Before we can think about maximizing them, we first need to understand what these solutions look like.

Today, we will cover the following learning outcome:
Write the general solution of a homogeneous linear difference equation in terms of its characteristic roots.

This process is the discrete-time analogue of solving linear homogeneous ordinary differential equations (ODEs) with constant coefficients, a method you've likely encountered in your physics studies. The core ideas—finding characteristic roots and using superposition—will be very familiar.

Let's begin.

1. What is a Homogeneous Linear Difference Equation?

A difference equation relates terms of a sequence to previous terms. The equations we are interested in are:

• Linear: The terms of the sequence appear in a linear fashion (no powers, products, or other functions).
• Homogeneous: There is no forcing term; the equation is equal to zero.
• Constant Coefficients: The coefficients that multiply the terms of the sequence are constants.

An equation of this type of order $n$ can be written as:
$x_t={\alpha }_1{x}_{t-1}+{\alpha }_2{x}_{t-2}+\cdots +{\alpha }_n{x}_{t-n}$
or, equivalently,
$x_{t+n}-{\alpha }_1{x}_{t+n-1}-\cdots -{\alpha }_n{x}_t=0$
where ${\alpha }_1,\dots ,{\alpha }_n$ are constants (which can be real or complex). The sequence is denoted by $x=(x_0,x_1,x_2,\dots )$.

To build some intuition, the following video introduces these concepts using the famous Fibonacci sequence as an example.

2. The Solution Method: The Characteristic Equation

The standard technique for solving these equations is to assume a solution of the form $x_t=z^t$, where $z$ is a complex number. This is analogous to assuming a solution of the form $e^{\lambda t}$ for ODEs.

Substituting $x_t=z^t$ into the rearranged equation $x_t-{\alpha }_1{x}_{t-1}-\cdots -{\alpha }_n{x}_{t-n}=0$, we get:
$z^t-{\alpha }_1{z}^{t-1}-\cdots -{\alpha }_n{z}^{t-n}=0$
Assuming $z\ne 0$, we can divide by $z^{t-n}$ to obtain a polynomial equation in $z$:
$z^n-{\alpha }_1{z}^{n-1}-\cdots -{\alpha }_n=0$
This is called the characteristic equation of the difference equation. The roots of this polynomial, known as the characteristic roots, are the key to constructing the general solution.

The following reading from a set of lecture notes on difference equations formalizes this procedure for a second-order equation. The logic extends directly to any order $n$.

3. Constructing the General Solution

By the Fundamental Theorem of Algebra, the characteristic equation of order $n$ has exactly $n$ roots in the complex plane, counting multiplicities. The form of the general solution depends on whether these roots are distinct or repeated.

A core concept we'll use is the principle of superposition: if you have multiple solutions to a homogeneous linear equation, any linear combination of them is also a solution.

Case 1: Distinct Roots

If the characteristic equation has $n$ distinct roots $z_1,z_2,\dots ,z_n$, then we have $n$ linearly independent solutions: $z_1^t,z_2^t,\dots ,z_n^t$.

The general solution is a linear combination of these basis solutions:
$x_t=c_1{z}_1^t+c_2{z}_2^t+\cdots +c_n{z}_n^t$
The constants $c_1,\dots ,c_n$ are determined by the first $n$ values of the sequence (the initial conditions), typically $x_0,x_1,\dots ,x_{n-1}$.

This is covered in Theorem 6.7(i) of the AAU lecture notes you just looked at.

Case 2: Repeated Roots

This case is particularly important for our goal, as the paper's main result involves all characteristic roots being identical.

If a root $z_i$ has a multiplicity of $m_i>1$, it means the factor $(z-z_i{)}^{m_i}$ appears in the characteristic polynomial. This single root must give rise to $m_i$ linearly independent solutions. These solutions are:
$z_i^t,t{z}_i^t,t^2{z}_i^t,\dots ,t^{m_i-1}{z}_i^t$
Again, this is analogous to the case of repeated roots in ODEs, which yield solutions like $e^{\lambda t},t{e}^{\lambda t},\dots$.

The following reading states this rule clearly.

Case 3: Complex Roots

The paper's problem is defined over the complex numbers, so we must be comfortable with complex roots. The general forms we've discussed already handle this perfectly. If $z_i$ is a complex root, the solution term is simply $c_i{z}_i^t$.

If the difference equation has real coefficients ${\alpha }_k$, then any complex roots of the characteristic equation must come in conjugate pairs ($z_i,{\bar{z}}_i$). In this scenario, one can combine the terms $c_i{z}_i^t+c_{i+1}{\bar{z}}_i^t$ and rewrite them using sines and cosines to get a real-valued solution, as shown in Theorem 6.7(iii) of the AAU notes. However, since the paper's problem is posed in $\mathbb{C}$, we will generally stick with the more direct complex exponential form.

4. The General Formula

We can now combine these cases to write the full general solution.

Let the characteristic equation of order $n$ have $k$ distinct roots $z_1,\dots ,z_k$ with corresponding multiplicities $m_1,\dots ,m_k$, where ${\sum }_{i=1}^k{m}_i=n$.

The general solution $x_t$ is a linear combination of the $n$ basis solutions derived from these roots. It can be written as:
$x_t={\sum }_{i=1}^k\left(c_{i,0}+c_{i,1}t+c_{i,2}{t}^2+\cdots +c_{i,m_i-1}{t}^{m_i-1}\right)z_i^t$
Or, more compactly:
$x_t={\sum }_{i=1}^k{P}_i(t)z_i^t$
where $P_i(t)$ is a polynomial in $t$ of degree $m_i-1$. The $n$ coefficients $c_{i,j}$ that define these polynomials are determined by the $n$ initial conditions $x_0,\dots ,x_{n-1}$.

This formula is the main takeaway of our lesson. It describes the entire space of possible solutions for any given homogeneous linear difference equation.

Conclusion

In this lesson, we have established the fundamental procedure for solving homogeneous linear difference equations with constant coefficients.

Key Takeaways:

• The solution method relies on finding the roots of the characteristic polynomial.
• The general solution is a linear combination of basis solutions derived from these roots.
• The form of the basis solutions depends on the roots and their multiplicities. A root $z_i$ with multiplicity $m_i$ contributes terms of the form $t^j{z}_i^t$ for $j=0,\dots ,m_i-1$.
• The final general solution for an $n$-th order equation is $x_t={\sum }_{i=1}^k{P}_i(t)z_i^t$, where the degrees of the polynomials $P_i(t)$ are determined by the root multiplicities.

Preview of the Next Lesson:
Now that we know the general form of the solution, we can start to analyze its behavior. In the next lesson, we will investigate how the solution evolves over time, paying special attention to the case of repeated roots. This will lay the groundwork for understanding why a configuration of identical roots, as mentioned in the paper, is a candidate for maximizing the solution's amplitude.