Discrete Mathematics

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 a₀, a₁, a₂, … is a formula (equation) that relates each term a_n to certain of its predecessors a₀, a₁, …, a_{n − 1}.

The initial conditions for such a recurrence relation specify the values of a₀, a₁, a₂, …, a_{n − 1}.

For example, recursive formula for the sequence

 

3, 8, 13, 18, 23

is

 

a₁ = 3, a_n = a_{n − 1} + 5, 2 ≤ n < ∞.

Here, a₁ = 3 is the initial condition.

Similarly, the infinite sequence

 

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

can be defined by the recursive formula

 

a₁ = 3, a_n = a_{n − 1} + 4, 2 ≤ n < ∞.

EXAMPLE 3.1

Find the sequence ...