term
is denoted by
Using
this notation, an example of a recurrence relation is given by
A Level Maths Notes: FP1 – Recurrence Relations and Closed Forms
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 if
is
expressed as a function of
so
that we can find
directly
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