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.

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

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.

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θ).

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.