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,…
A recurrence relation is in closed form ifis expressed as a function ofso that we can find directly 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.
for the expression andfrom the question. Substitute these into (1) to obtain