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 the
term is denoted by
Using 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 if
is expressed as a function of
so that we can finddirectly given any value of
without having to find all the preceding terms. This is the more useful form of the relation. For any recurrence relation of the form
with
given,
(1) Often we can guess the closed form and prove it by induction.
For the sequence given above: Prove
First we prove
which is true.
Assume
Prove
Hence
for the expression
and
from the question. Substitute these into (1) to obtain