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