A recurrence relation relates the nth term of a sequence to its predecessors. These relations are related to recursive algorithms.
3.1 RECURRENCE RELATIONS
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
Here, a1 = 3 is the initial condition.
Similarly, the infinite sequence
can be defined by the recursive formula
Find the sequence ...