3

Recurrence Relations

A recurrence relation relates the nth 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 a0, a1, a2, … is a formula (equation) that relates each term an to certain of its predecessors a0, a1, …, an 1.

The initial conditions for such a recurrence relation specify the values of a0, a1, a2, …, an 1.

For example, recursive formula for the sequence

 

3, 8, 13, 18, 23

is

 

a1 = 3, an = an − 1 + 5, 2 ≤ n < ∞.

Here, a1 = 3 is the initial condition.

Similarly, the infinite sequence

 

3, 7, 11, 15, 19, 23, …

can be defined by the recursive formula

 

a1 = 3, an = an − 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.