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