# 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 Recurrence Systems

• 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.

## Solving Recurrence Systems with Non-Homogeneous Terms

• 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.

## Applications of Recurrence Systems

• 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.