## 3

## Recurrence Relations

A recurrence relation relates the *n*th term of a sequence to its predecessors. These relations are related to recursive algorithms.

##### 3.1 RECURRENCE RELATIONS

**Definition 3.1**

A **recurrence relation** for a sequence *a*_{0}, *a*_{1}, *a*_{2}, … is a formula (equation) that relates each term *a*_{n} to certain of its predecessors *a*_{0}, *a*_{1}, …, *a*_{n} _{−} _{1}.

The **initial conditions** for such a recurrence relation specify the values of *a*_{0}, *a*_{1}, *a*_{2}, …, *a*_{n} _{−}_{ 1}.

For example, recursive formula for the sequence

is

*a*

_{1}= 3,

*a*

_{n}=

*a*

_{n − 1}+ 5, 2 ≤

*n*< ∞.

Here, *a*_{1} = 3 is the initial condition.

Similarly, the infinite sequence

can be defined by the recursive formula

*a*

_{1}= 3,

*a*

_{n}=

*a*

_{n − 1}+ 4, 2 ≤

*n*< ∞.

**EXAMPLE 3.1**

Find the sequence ...

Get *Discrete Mathematics* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.