Recurrence relation

From Citizendium, the Citizens' Compendium
Jump to: navigation, search
This article is a stub and thus not approved.
Main Article
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.

A recurrence relation is a relation between an entry in a sequence of numbers or other mathematical objects and preceding entries in the sequence. An explicit relation is one in which a term is defined in terms of preceding values, as opposed to an implicit definition.

For example, assume that you put 100 dollars on a bank account and that the bank pays you 6% compound interest every year. After one year, you will have the original 100 dollars plus 6 dollars interest, which makes 106 dollars. After two years, you have $ 112.06 (the 106 dollars you have after one year, plus 6% of $ 106 interest). The amount you have in your account grows according to the sequence 100, 106, 112.06, 118.18, …. This sequence is defined by the rule that every year you have the same amount as the previous year plus 6% of what you had the previous year. This is a recurrence relation in words. However, recurrence relations are usually formulated as a mathematical formula. As a first step, we can rewrite the rule as: in year n + 1, you have the same amount as in year n plus 6% of what you had in year n. Now, introduce the symbol an to stand for the amount in the account in year n. Then, the recurrence relation becomes an+1 = an + 0.06an. This is an explicit relation because the next term in the sequence is given as a function of preceding terms (here in fact just one preceding term.) The solution to this relation is an = (1.06)na0, where a0 is the initial amount, here $100.


The factorial function satisfies the relation

The Fibonacci numbers satisfy a recurrence relation in which each term depends on the two preceding, so the first two values need to be specified to make the definition complete:

More generally, a Lucas sequence satisfies

for constants P and Q.

An example of a recurrence relation with more than one variable is given by the binomial coefficients

which gives the rule of formation of Pascal's triangle, where the values on the n-th row depend on the values on the row above, with the further conditions

The Somos sequence is defined by the implicit relation

which rather surprisingly generates a sequence of integers from the starting values 1,1,1,1.