Recurrence Relations and Closed Forms

It's only fair to share...Share on FacebookTweet about this on TwitterPin on PinterestShare on Google+Share on RedditEmail this to someone

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 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.

Assume

Prove

Hence

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

Comments are closed.