Repeated Roots and Solutions

Hello! Welcome back to our course.

In our first lesson, we established the general form for the solution of an $n$-th order homogeneous linear difference equation. We saw that the solution is a linear combination of terms derived from the roots of the characteristic polynomial, and we noted the special form for repeated roots:
$x_t={\sum }_{i=1}^k{P}_i(t)z_i^t$
where $P_i(t)$ is a polynomial whose degree depends on the multiplicity of the root $z_i$.

Today's lesson focuses on the "why" behind this formula. Our learning outcome is to:
Explain how solutions behave when characteristic roots have multiplicity, leading to terms of the form $t^k\cdot r^t$.

Instead of just accepting the formula, we will derive it. Understanding its origin is crucial for appreciating the paper's main result, which, as we'll see, involves a scenario with maximally repeated roots. Your background in solving ODEs in physics will be helpful here, as the underlying mathematical challenge and the form of the solution are directly analogous.

1. The Problem: Degeneracy and Linear Independence

Let's consider a simple second-order equation where the characteristic polynomial has two identical roots, $z_1=z_2=z$.

If we followed the procedure for distinct roots, we would propose two solutions, $x_t^{(1)}=z^t$ and $x_t^{(2)}=z^t$. The general solution would be a linear combination:
$x_t=c_1{z}^t+c_2{z}^t=(c_1+c_2)z^t=C{z}^t$
This is a problem. A second-order equation should have a solution space of dimension two, meaning we need two linearly independent basis solutions to be able to satisfy any two initial conditions ($x_0,x_1$). The form $C{z}^t$ has only one degree of freedom, not two. We are missing a second, independent solution.

The following short video clip frames this exact issue in the context of ODEs. The reasoning is identical for difference equations.

As the video suggests, the "trick" is to introduce a solution of the form $t\cdot z^t$. But why this specific form? Let's derive it.

2. Derivation 1: The Perturbation Method

One of the most elegant ways to understand the origin of the $t\cdot z^t$ term is to view a repeated root as the limit of two distinct roots as they approach each other.

Consider a second-order characteristic equation with two distinct roots ${\rho }_1$ and ${\rho }_2$. The general solution is:
$x_t=A{\rho }_1^t+B{\rho }_2^t$
Now, let's imagine these roots are very close to a central value $\lambda$, such that ${\rho }_1=\lambda +ϵ$ and ${\rho }_2=\lambda -ϵ$. What happens as we let $ϵ\to 0$?

The following resource provides a step-by-step derivation using this idea. It solves for the coefficients $A$ and $B$ in terms of initial conditions and then evaluates the limit of the entire solution as $ϵ\to 0$.

This method beautifully demonstrates how the solution $(A+Bt){\lambda }^t$ emerges as a continuous transformation from the distinct-root case.

3. Derivation 2: Reduction of Order

Another standard technique, which you may have seen for ODEs, is called "reduction of order." We know one solution is $x_t^{(1)}={\lambda }^t$. We can guess the second solution has the form $x_t^{(2)}=y_t{\lambda }^t$ and solve for the unknown sequence $y_t$.

Let's apply this to the second-order equation with a repeated root $\lambda$. The equation can be written as:
$x_{t+2}-2\lambda x_{t+1}+{\lambda }^2{x}_t=0$
Substituting $x_t=y_t{\lambda }^t$ gives:
$(y_{t+2}{\lambda }^{t+2})-2\lambda (y_{t+1}{\lambda }^{t+1})+{\lambda }^2(y_t{\lambda }^t)=0$
Dividing by ${\lambda }^{t+2}$ (assuming $\lambda \ne 0$), we get a much simpler equation for $y_t$:
$y_{t+2}-2y_{t+1}+y_t=0$
This is a simple recurrence. If we let $z_t=y_{t+1}-y_t$, the equation becomes $z_{t+1}-z_t=0$, which means $z_t$ is a constant, say $D$. So, $y_{t+1}-y_t=D$. This is an arithmetic progression, whose solution is $y_t=C+Dt$.

Therefore, our full solution is:
$x_t=y_t{\lambda }^t=(C+Dt){\lambda }^t=C{\lambda }^t+D(t{\lambda }^t)$
This confirms that the two linearly independent solutions are ${\lambda }^t$ and $t{\lambda }^t$. The same resource you just read also walks through this method.

4. The General Case: Higher Multiplicities

These derivations explain the case for a root with multiplicity $m=2$. The pattern generalizes. If a root $\lambda$ has multiplicity $m$, it contributes $m$ linearly independent solutions to the general solution:
${\lambda }^t,t{\lambda }^t,t^2{\lambda }^t,\dots ,t^{m-1}{\lambda }^t$
The general solution is a linear combination of all such basis solutions from all distinct roots.

The following resource provides a formal theorem and a proof for this general case. The proof is more abstract and relies on differentiating the characteristic polynomial, but it rigorously establishes the pattern for any multiplicity.

5. Behavior of Solutions with Repeated Roots

The presence of the polynomial term $t^k$ dramatically influences the long-term behavior of the solution $x_t$. Let's analyze the term $t^k{\lambda }^t$:

• If $|\lambda |>1$: The term ${\lambda }^t$ already grows exponentially. The polynomial $t^k$ further accelerates this growth. The solution diverges rapidly.
• If $|\lambda |<1$: The exponential decay of ${\lambda }^t$ is stronger than the polynomial growth of $t^k$. For any $k\ge 0$ and $|\lambda |<1$, we have ${\lim }_{t\to \infty }{t}^k{\lambda }^t=0$. The solution converges to zero.
• If $|\lambda |=1$: This is a particularly interesting case.
  • Without repetition ($k=0$), the solution ${\lambda }^t$ is bounded (it oscillates on the unit circle in the complex plane).
  • With repetition ($k>0$), the term $t^k{\lambda }^t$ is unbounded. The magnitude $|t^k{\lambda }^t|=t^k$ grows polynomially with $t$.

This last point is critical for the paper you are studying. The problem is to maximize $|x_t|$. The presence of repeated roots on the boundary of the allowed disk ($|\lambda |=r$) introduces a mechanism for polynomial growth, which would otherwise not be present. This makes such configurations prime candidates for achieving the maximum amplitude.

Conclusion

In this lesson, we delved into the mathematical origins of the solution form for difference equations with repeated characteristic roots.

Key Takeaways:

• Repeated roots in the characteristic equation lead to a degeneracy, requiring additional, linearly independent solutions.
• These solutions take the form $t^k{\lambda }^t$. We derived this using both a limit-based perturbation method and an algebraic reduction-of-order method.
• For a root $\lambda$ with multiplicity $m$, the general solution includes a polynomial in $t$ of degree $m-1$: $(c_0+c_{1}t+\cdots +c_{m-1}{t}^{m-1}){\lambda }^t$.
• The polynomial factor $t^k$ causes the solution's amplitude to grow over time when $|\lambda |\ge 1$, a key behavior when searching for a maximum amplitude.

Preview of the Next Lesson:
We now have a solid understanding of the structure of solutions to these equations. In the next lesson, we will synthesize this knowledge to formally state the optimization problem at the heart of the paper: how to maximize $|x_t|$ at a specific time $t$, given that the characteristic roots are constrained to a disk of radius $r$ and the initial conditions are also constrained.