Linear Recurrences and Diagonalization

students, have you ever noticed how a rule that uses the previous step can create a whole pattern over time? 📈 A linear recurrence does exactly that. It tells you how to build the next term of a sequence from earlier terms using addition and multiplication by constants. This lesson shows how linear recurrences connect to matrices, diagonalization, and dynamical systems, which are all powerful tools in linear algebra.

What is a linear recurrence?

A recurrence relation is a rule that defines each term of a sequence from earlier terms. A linear recurrence is one where the new term is a linear combination of previous terms. For example,

$$a_{n+2} = 3a_{n+1} - 2a_n$$

is a linear recurrence because $a_{n+2}$ depends on $a_{n+1}$ and $a_n$ in a linear way. There are no squares, products like $a_na_{n+1}$, or weird nonlinear expressions.

The numbers you start with are called initial conditions. For the recurrence above, you would need two starting values, such as $a_0$ and $a_1$, to generate the whole sequence.

A familiar example is the Fibonacci sequence, defined by

$$F_{n+2} = F_{n+1} + F_n$$

with $F_0 = 0$ and $F_1 = 1$. Each new term is the sum of the two previous terms. This simple rule appears in patterns in nature, computer science, and modeling growth.

The key idea is this: a recurrence turns a sequence into a step-by-step process. Instead of listing every term, you use a rule to move from one step to the next. That is exactly the kind of thinking that leads to dynamical systems. 🔄

Writing recurrences as matrix systems

Many linear recurrences can be rewritten using matrices. This is important because matrices let us use linear algebra tools to study long-term behavior.

Suppose we have

$$a_{n+2} = 3a_{n+1} - 2a_n$$

Define a state vector

$$\mathbf{x}_n = \begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix}$$

Then the recurrence can be rewritten as

$$\mathbf{x}_{n+1} = \begin{bmatrix} 3 & -2 \\ 1 & 0 \end{bmatrix}\mathbf{x}_n$$

This matrix equation says that the next state comes from multiplying the current state by a matrix. If we call the matrix $A$, then

$$\mathbf{x}_{n+1} = A\mathbf{x}_n$$

and repeated steps give

$$\mathbf{x}_n = A^n\mathbf{x}_0$$

This is a discrete dynamical system because time moves in separate steps: $n = 0,1,2,3,\dots$. Each step applies the same transformation again and again.

A matrix form is useful because it turns the recurrence into a problem about powers of a matrix. Instead of computing term by term forever, we can study $A^n$. That opens the door to diagonalization.

Why diagonalization helps

Diagonalization is a method that can make matrix powers much easier to compute. If a matrix $A$ can be written as

$$A = PDP^{-1}$$

where $D$ is diagonal, then

$$A^n = PD^nP^{-1}$$

and powers of a diagonal matrix are easy, because you just raise each diagonal entry to the $n$th power.

Why does this matter for recurrences? Because the matrix that describes a recurrence often has eigenvalues and eigenvectors that reveal the sequence’s behavior. If the matrix is diagonalizable, you can often find a closed formula for the sequence.

For example, if the matrix has eigenvalues $\lambda_1$ and $\lambda_2$, then the terms often look like combinations of powers such as

$$c_1\lambda_1^n + c_2\lambda_2^n$$

This is a huge simplification compared to computing every term separately.

Diagonalization is especially powerful when the recurrence has constant coefficients. The recurrence itself does not change from step to step, so the same matrix works every time. That regularity is what makes linear algebra tools so effective.

Example: solving a recurrence with eigenvalues

Let’s look at

$$a_{n+2} = 3a_{n+1} - 2a_n$$

with initial values $a_0$ and $a_1$. We already rewrote this as

$$\mathbf{x}_{n+1} = A\mathbf{x}_n, \quad A = \begin{bmatrix} 3 & -2 \\ 1 & 0 \end{bmatrix}$$

To understand the long-term pattern, we find the eigenvalues of $A$. The characteristic polynomial is

$$\det(A-\lambda I) = \det\begin{bmatrix} 3-\lambda & -2 \\ 1 & -\lambda \end{bmatrix} = (3-\lambda)(-\lambda)+2$$

which simplifies to

$$\lambda^2 - 3\lambda + 2 = 0$$

Factoring gives

$$ (\lambda-1)(\lambda-2)=0 $$

So the eigenvalues are $\lambda = 1$ and $\lambda = 2$.

That tells us the sequence will be built from powers of $1$ and $2$. So the general form is

$$a_n = c_1(1)^n + c_2(2)^n = c_1 + c_2 2^n$$

We use the starting values to determine $c_1$ and $c_2$. If $a_0$ and $a_1$ are given, then

$$a_0 = c_1 + c_2$$

and

$$a_1 = c_1 + 2c_2$$

Subtracting gives

$$a_1 - a_0 = c_2$$

Then

$$c_1 = a_0 - c_2$$

This is a complete solution. The recurrence is now expressed as a formula instead of a step-by-step process.

A nice check is to see that the recurrence matches the formula. If $a_n = c_1 + c_2 2^n$, then

$$a_{n+2} = c_1 + c_2 2^{n+2}$$

and

$$3a_{n+1} - 2a_n = 3(c_1 + c_2 2^{n+1}) - 2(c_1 + c_2 2^n) = c_1 + c_2 2^{n+2}$$

So the formula works. ✅

Connection to dynamical systems

Linear recurrences are a special case of discrete dynamical systems. In a dynamical system, you start with a state and apply a rule repeatedly. For linear recurrences, the rule is linear and repeated at each step.

The matrix equation

$$\mathbf{x}_{n+1} = A\mathbf{x}_n$$

is the simplest example of a linear dynamical system. The matrix $A$ acts like a machine that updates the state each step. Depending on the eigenvalues of $A$, the system may grow, shrink, or stabilize.

For instance:

If an eigenvalue satisfies $|\lambda| > 1$, the corresponding component tends to grow.
If $|\lambda| < 1$, the corresponding component tends to shrink toward $0$.
If $|\lambda| = 1$, the behavior may stay bounded or oscillate.

This helps explain why diagonalization is so useful. Once the system is expressed in eigen-directions, each piece evolves independently. That makes the long-term behavior much easier to predict.

A real-world example is a population model with two groups, such as young and adult animals. If next year’s populations depend linearly on this year’s populations, then the system can be written as a matrix recurrence. Studying the eigenvalues helps predict whether the population grows, declines, or settles into a pattern.

A second example: Fibonacci and matrix power

The Fibonacci recurrence is

$$F_{n+2} = F_{n+1} + F_n$$

with $F_0 = 0$ and $F_1 = 1$. Write

$$\mathbf{v}_n = \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}$$

Then

$$\mathbf{v}_{n+1} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\mathbf{v}_n$$

This means

$$\mathbf{v}_n = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \mathbf{v}_0$$

The Fibonacci matrix is diagonalizable, so its powers can be studied using its eigenvalues. Those eigenvalues are related to the golden ratio and its conjugate. This is why the Fibonacci numbers grow in a very regular way.

Even if you do not compute every step by hand, the matrix view explains the structure behind the sequence. That is a central goal of linear algebra: not just calculating, but understanding the pattern. 🌟

Conclusion

Linear recurrences are rules that generate sequences from previous terms using linear combinations. They become especially powerful when rewritten as matrix equations, because then linear algebra tools such as eigenvalues and diagonalization can be used. This creates a direct bridge from sequences to dynamical systems.

students, the main takeaway is that a recurrence is not just a list of numbers. It is a system that evolves over time. By using matrices, you can study its behavior, find closed formulas, and predict long-term trends. That is why linear recurrences are an important part of diagonalization and dynamical systems.

Study Notes

A linear recurrence defines each new term as a linear combination of previous terms.
A recurrence needs initial conditions to start the sequence.
Example: $a_{n+2} = 3a_{n+1} - 2a_n$.
The Fibonacci sequence is a classic recurrence: $F_{n+2} = F_{n+1} + F_n$.
Many recurrences can be written as a matrix system $\mathbf{x}_{n+1} = A\mathbf{x}_n$.
Repeated application gives $\mathbf{x}_n = A^n\mathbf{x}_0$.
If $A$ is diagonalizable, then $A = PDP^{-1}$ and $A^n = PD^nP^{-1}$.
Diagonalization makes matrix powers easier because diagonal entries are easy to raise to powers.
Eigenvalues help predict whether a system grows, shrinks, or stays bounded.
Linear recurrences are a type of discrete dynamical system because they move forward in steps.