Sequences and Series: Solving recurrence systems

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.