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 the O’Reilly learning platform.

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