Recurrence Relations

A recurrence relation uses each term or maybe several terms in a sequence to calculate succeeding terms. If the nth term is denoted by u-n then theterm is denoted byUsing this notation, an example of a recurrence relation is given by

If the first term of this sequence is 6

The second term

The third term is

The fourth term is

The sequence defined by the recurrence relation is 6, 31, 181, 1081,...

Closed Form

A recurrence relation is in closed form ifis expressed as a function ofso that we can finddirectly given any value ofwithout having to find all the preceding terms. This is the more useful form of the relation. For any recurrence relation of the formwith given,(1) Often we can guess the closed form and prove it by induction.

For the sequence given above: Prove

First we provewhich is true.

Assume

Prove

Hence

for the expressionandfrom the question. Substitute these into (1) to obtain