Sequences and Series: Solving recurrence systems

Understanding Recurrence Systems

A recurrence system is system of equations where the result of one equation is used as an input for the next.
Recurrence systems are often used in modelling sequences and series.
The order of a recurrence system is the number of steps back it depends on. A system depending on the previous two steps is second order, and so on.
The simplest form of a recurrence system is the first order linear recurrence relation: a(n) = pa(n-1) + q, where p and q are constants.
A higher order recurrence system could look like this: a(n) = pa(n-1) + qa(n-2) + r, where p, q, and r are constants, and this is a second order system.

Solving a recurrence system involves finding a general term a(n) that can calculate any term in the sequence without referring to previous terms.
The foundation of solving recurrence system lies in understanding the concept of a characteristic equation. The characteristic equation of the recurrence relation a(n) = pa(n-1) + qa(n-2) is r^2 - pr - q = 0.
The roots of the characteristic equation provide valuable information about the solution to the recurrence system.
When both roots are real and distinct, r1 and r2, the general form of the solution is a(n) = kr1^n + lr2^n.
When the characteristic equation has repeated roots, r1, the general form of the solution is a(n) = (kr + l)n^r.
When the roots are complex, arranged as p ± qi, the general solution is a(n) = r^n[kcos(nθ) + lsin(nθ)], where r = sqrt(p^2 + q^2) and θ = tan^-1(q/p).
Constants k and l can be found by using the initial conditions of the problem.

In many realistic situations, the sequence is subjected to forces external to the system, leading to non-homogeneous recurrence relations.
The procedure to solve such systems involves finding the complementary function (solution of the homogeneous part) and a particular solution (solution of the non-homogeneous part).
We find the final solution by adding together the complementary function and the particular solution.

Recurrence systems, due to their inherent iterative nature, are useful in modelling various practical phenomena including population growth, economic behaviours, and biological processes.
Being able to solve recurrence systems opens up the ability to analyse complex dynamic systems in several fields including mathematics, physics, economics, and computer science.