Sequences and Series: Recurrence relations

Sequences and Series: Recurrence relations

Understanding Recurrence Relations

  • A recurrence relation is an equation that defines a sequence based on a rule describing how some terms in the sequence are related to earlier terms.
  • In mathematics, the most common type of recurrence relation is called a linear recurrence relation. The sequence defined by such a relation can often be solved explicitly.
  • Recurrence relations, sometimes called difference equations, are functions that give the terms of sequences by defining each term in terms of one or more of the preceding terms.
  • A recurrence relation permits to calculate the progression of a sequence using a rule and thus “recurring” to previous terms.

First-Order Recurrence Relations

  • Recall that a first-order recurrence relation is of the format un+1 = fun, where f is a given function. The recursive form of the sequence is defined by the relation un = an – bnun – 1.

Non-Linear Recurrence Relations

  • Non-linear recurrence relations involve one or more of the previous values raised to a power greater than one.
  • Solving non-linear recurrence relations usually require advanced techniques and are more complex than linear recurrence relations.

Solving Recurrence Relations

  • You may use the method called generating functions to solve a recurrence relation. This involves creating a power series from the recurrence relation and solving for the closed-form expression.
  • First, identify the characteristic equation for the relation, which is derived from the coefficients of the terms in the recurrence relation.
  • Then, root the characteristic equation and substitute these roots into the general solution to get the exact solution.
  • Use the initial conditions to find the particular solution to a recurrence relation.

General Behaviour of Recurrence Relations

  • For constant coefficient linear recurrence relations, if the roots of the characteristic equation are real and distinct, the general term is in the form Anr^n.
  • If the roots are real and repeated, the general term is of the form (An + Bn)r^n.
  • If the roots are complex, the general term is of the form r^n(An cos nθ + Bn sin nθ).

Applications of Recurrence Relations

  • Recurrence relations are common in computer science, where they are used to determine the time complexity of algorithms.
  • They are also useful in physics, engineering, and other fields, where they can model natural phenomena and physical systems.