Solving Linear Recurrence Relation via triangularization

of Matrix and some insights on long term behaviour of

linear recurrence relation

Abstract—I present a simple and efficient method for solving linear recurrence relation
where multiple recurrence relation is related to each other via the previous terms. And
provide some insights on the long term behaviour of the recurrence relation based on
their first term.

Index Terms—Recurrent sequence, Diagonalization, Eigenvector, Eigenvalues, Unitary

matrix, triangular matrix, Schur Triangularization

Introduction
Linear recurrence relations are fundamental tools in mathematics, with applications spanning
various fields such as computer science, physics, biology, and economics. These relations
describe sequences where each term is defined as a linear combination of previous terms,
making them invaluable for modeling dynamic systems and solving combinatorial problems.
One notable figure who extensively utilized recurrence relations is Donald E. Knuth, a
renowned computer scientist and mathematician. In his seminal work, The Art of Computer
Programming, Knuth employed recurrence relations to analyze the efficiency of algorithms,
particularly in the context of sorting and searching. By formulating recurrence relations to
describe the time complexity of algorithms like Merge Sort and Quick Sort, Knuth provided
a rigorous framework for understanding algorithmic behavior and performance.

One of the prominent contemporary researchers in the field of recurrence relations is

Anthony G. Shannon, whose work has significantly advanced our understanding of linear
recurrence sequences and their applications. Shannon, along with his collaborators, has
explored the algebraic and combinatorial properties of recurrence relations, particularly in the
context of Fibonacci-like sequences and their generalizations. His research has extended the
classical theory of recurrence relations to include partial recurrence relations and matrix
recurrence relations, which have applications in operations research, inventory control, and
number theory.
Prasad and Mahato have explored the matrix representations of generalized Fibonacci
sequences, demonstrating how these matrices can be used to derive Binet-like formulas,
Catalan identities, and trace sequences.
Their work extends the classical theory of Fibonacci numbers by introducing new families of
sequences, such as the generalized Leonardo numbers and k-Horadam-like sequences,
which are defined by higher-order recurrence relations. These sequences not only preserve
the elegant properties of the Fibonacci sequence but also introduce new identities, generating
functions, and matrix representations that have broad applications in combinatorics, number
theory, and cryptography

Maxwell Lachut and Benjamin Keigwin explore the principles and applications of the Real
and Complex Spectral Theorems, which are fundamental in linear algebra and functional
analysis. Lachut and Keigwin explored the use of spectral theorem from Multivariable
Calculus, Principal Component Analysis, Electrical Network to the use of complex spectral
theorem in Schrodinger equation.
Generally the linear recurrence relations are solved using the matrix method where we
simplify the problem of finding the nth term of a linear recurrence relation into finding the
nth power of a square matrix.
Many linear recurrence relations such as the Lucas or Fibonacci equation are solved using the
matrix method where the matrices are symmetric and because of the Spectral theorem they
are unitary diagonalizable.

Matrix methods provide a structured and computationally efficient framework for solving
recurrence relations, particularly when combined with diagonalization techniques.
Usually such linear recurrence relations are solved using generating functions and
diagonalization of matrices.

, a great example of which is the fibonacci sequence which is solved by converting the
general fibonacci equation into the following matrix equation

Similarly multiplying the matrix on both sides yield us the following matrix equation.
Through the process of diagonalization we can find the nth power of this matrix as this
matrix is symmetric, and we know according to spectral theorem that a symmetric matrix of
order n has n linearly independent and orthogonal eigenvectors, using which the matrix can
be diagonalised and the nth power of it can be easily calculated

But what to do if the matrix is not diagonalizable ?

Triangularisation of a matrix
Bhatia Rajendra and Radha Mohan explored the concept of triangularization of matrices, a
fundamental process in linear algebra that transforms a given matrix into an upper or lower
triangular form. Their paper provides a comprehensive analysis of the conditions under which
a matrix can be triangularized, emphasizing the role of eigenvalues and eigenvectors in this
process. They demonstrated that for a matrix to be triangularizable, it must satisfy certain
spectral properties, particularly in relation to its eigenvalues. Furthermore, they highlighted
the importance of similarity transformations in achieving triangularization, showing how a
matrix can be expressed in triangular form by conjugation with an appropriate invertible
matrix. Their work also delves into the connection between triangularization and Schur
decomposition, a key result in matrix theory that guarantees the existence of a unitary
transformation to triangularize any complex square matrix.

Schur's Triangularization Theorem states that any square complex matrix A is unitarily
similar to an upper-triangular matrix T. This means there exists a unitary matrix U such
that U*AU = T.

For solving the recurrence relation where the matrix is not diagonalizable, instead of
diagonalization, triangularization of the matrix can help us find the nth term of a linear
recurrence relation.
In this work I have developed a method which can help solve any general
linear recurrence relation of finite arbitrary order with finite number of
variables.

Demonstration of the method:

Without loss of generality let's assume there is a linear recurrent sequence of order 1 in three
variables (A,B and C).

Here the recurrence relation can be modelled into a matrix equation.

Let's denote the coefficient matrix on the left side of equation (1) as R for further
convenience.

Similarly we can obtain:

Using Schur's triangular decomposition method we can decompose the coefficient matrix R
into an upper triangular matrix and a unitary matrix and its inverse(transpose in case of
unitary matrix).
and ,

Let's denote the upper triangular matrix in the right hand side as T.

Now,
𝑡ℎ
To find the 𝑛 power of the upper triangular matrix T we can separate the matrix T into a
diagonal matrix D and a strictly upper triangular matrix Q

and then proceed with the binomial theorem to find the value of

We can use binomial theorem to expand in terms of

Notice that the expansion has only three terms because Q is a strictly upper triangular matrix
of order 3.

Which yields us the following result.

Now let's assume this sum to be,

Where,
 𝑡ℎ 𝑛𝑑
From equation 5 𝑎𝑛𝑑 2

𝑡ℎ
Now, we are just a matrix multiplication away to find the 𝑛 term of a linear recurrence
sequence.

𝑡ℎ
This method now can be easily generalised for finding the 𝑚 order linear recurrence
relations in n variables.

Insights on long term behaviour of linear recurrence

relation based on its first term.
Again without the loss of generality, let's assume we have modelled our recurrence relation
into the following matrix equation

Where the square matrix on the left hand side is the coefficient matrix.

Where is the “first term vector” 𝐾0.

Now let's assume that the vector 𝐾0 belongs to the eigenspace of the coefficient matrix.
Then the sequence 𝐴𝑛 𝐵𝑛 and 𝐶𝑛 converges if the vector 𝐾0 can be written in the following
linear combination,
𝐾0= 𝑎1𝑉1+𝑎2𝑉2+𝑎3𝑉3+ ……..+𝑎𝑛𝑉𝑛

Where and 𝑉𝑖 are linearly independent eigenvectors of the coefficient matrix.

𝑡ℎ
The “𝑛 term vector” let's call it 𝐾𝑛 converges to

where 𝑉𝑖 are eigenvectors corresponding to eigenvalue 1.

This can also be verified through the following example.

Let's assume we have given a recurrence relation

Lets the first term vector be 𝑉0 which is the eigenvector of the coefficient matrix
corresponding to the eigenvalue 1

Now, if 𝑉0= where 𝐴0 = 𝑣1, 𝐵0 = 𝑣2 and 𝐶0 = 𝑣3

Equating the value of 𝐴0, 𝐵0 𝑎𝑛𝑑 𝐶0 in the recurrence relation gives us
The value of 𝐴1, 𝐵1 𝑎𝑛𝑑 𝐶1 which is same as 𝑣1, 𝑣2 and 𝑣3

Even if the first term vector is a linear combination of several vectors corresponding to
eigenvalue 1 the second term vector will be equal to the first term vector.
REFERENCES

1.​ Shannon, Anthony G., Peter J.-S. Shiue, Shen C. Huang, Ali Balooch and
Yu-Chung Liu. “Some infinite series summations involving linear recurrence
relations of order 2 and 3.” Notes on Number Theory and Discrete Mathematics
(2024): n. pag.

2.​ Prasad, Kalika and Hrishikesh Mahato. “On the generalized Fibonacci like
sequences and matrices.” Annales Mathematicae et Informaticae (2023): n.
Pag.

3.​ Lachut, M. and Keigwin, B., 2023. Applications of the Spectral Theorem: Utilizing
Eigenvalues and Eigenvectors. Journal of Student Research, 12(4).
4.​ (2008). Recurrence Relations. In: Mathematics for the Analysis of Algorithms.
Progress in Computer Science and Applied Logic (PCS), vol 1. Birkhäuser
Boston. https://doi.org/10.1007/978-0-8176-4729-2_2
5.​ Dmytryshyn, A. (2023). Schur decomposition of several matrices. Linear and
Multilinear Algebra, 72(8), 1346–1355.
https://doi.org/10.1080/03081087.2023.2177246
6.​ Mariconda, C., Tonolo, A. (2016). Linear Recurrence Relations. In: Discrete
Calculus. UNITEXT(), vol 103. Springer, Cham.
https://doi.org/10.1007/978-3-319-03038-8_10
7.​ Ranđelović, B., Nikolić, S., Milovanović, A. and Ilić, I., 2022. LINEAR
RECURRENCE RELATONS AND ORDINARY GENERATING FUNCTIONS
APPLIED ON MODELING PROCESSES IN CONTROL THEORY. Facta
Universitatis, Series: Automatic Control and Robotics, 1(1), pp.015-024.
8.​ Rydén, Christoffer. "Generating Functions: Powerful Tools for Recurrence
Relations. Hermite Polynomials Generating Function." (2023).
9.​ Kiliç, E., Tasci, D. and Haukkanen, P., 2010. On the generalized Lucas
sequences by Hessenberg matrices. Ars Combin, 95, pp.383-395.
10.​Johnson, Robert C. "Fibonacci numbers and matrices." Durham University
(2009).