Recurrence relation

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 a_n to stand for the amount in the account in year n. Then, the recurrence relation becomes a_n+1 = a_n + 0.06a_n. 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 a_n = (1.06)ⁿa₀, where a₀ is the initial amount, here $100.

Examples

The factorial function satisfies the relation

$n!=n\cdot (n-1)!\,$

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:

$F_{n}:={\begin{cases}0&{\mbox{if }}n=0;\\1&{\mbox{if }}n=1;\\F_{n-1}+F_{n-2}&{\mbox{if }}n>1.\\\end{cases}}$

More generally, a Lucas sequence satisfies

$X_{n}(P,Q)=PX_{n-1}(P,Q)-QX_{n-2}(P,Q)\,$

for constants P and Q.

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

${\binom {n}{r}}={\binom {n-1}{r}}+{\binom {n-1}{r-1}}$

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

${\binom {n}{0}}={\binom {n}{n}}=1.\,$

The Somos sequence is defined by the implicit relation

$a_{n}a_{n-4}=a_{n-1}a_{n-3}+a_{n-2}^{2}$

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