How are recurrence relations used in mathematics and computer science?

[Greg Bernhardt]

Definition/Summary

A recurrence relation is an equation which defines each term of a sequence as a function of preceding terms.

The most well-known are those defining the Fibonacci numbers and the binomial coefficients.

An ordinary differential equation can be considered as a recurrence relation on the sequence of nth derivatives of a function (in which the 0th derivative is the function itself), and if linear can be solved using the characteristic polynomial method.

Equations

Fibonacci numbers:

Each Fibonacci number is the sum of the two preceding numbers, starting with 1 and 1:

$$F_n\ =\ F_{n-1}\ +\ F_{n-2}$$

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

Binomial coefficients (Pascal's triangle):

Each binomial coefficient is the sum of the two coefficients "diagonally below", starting with 1:

$$\left(\begin{array}{c}n\\k\end{array}\right)\ =\ \left(\begin{array}{c}n - 1\\k\end{array}\right)\ +\ \left(\begin{array}{c}n-1\\k-1\end{array}\right)$$

1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1; ...

Extended explanation

Characteristic polynomial:

This is not the same as the characteristic polynomial of a matrix or matroid

In a linear differential equation, the derivative may be replaced by an operator, D, giving a polynomial equation in D:

$$\sum_{n\,=\,0}^m\,a_n\,\frac{d^ny}{dx^n}\ =\ 0\ \mapsto\ \left(\sum_{n\,=\,0}^m\,a_n\,D^n\right)y\ =\ 0$$

Similarly, in a linear recurrence relation, the nth term may be replaced by an nth power:

$$\sum_{n\,=\,0}^m\,a_{k+n}\,P_{k+n}\ =\ 0\ \mapsto\ \sum_{n\,=\,0}^m\,a_n\,x^n\ =\ 0$$

If this polynomial has distinct (different) roots $r_1,\dots,r_m$:

$$\prod_{n\,=\,1}^m(D\,-\,r_n)\ =\ 0$$ or $$\prod_{n\,=\,1}^m(x\,-\,r_n)\ =\ 0$$

then the general solution is a linear combination of the solutions of each of the equations:

$$\left(D\,-\,r_n\right)y\ =\ 0$$ or $$P_{k+1}\ -\ r_nP_k\ =\ 0$$

which are the same as $$\frac{dy}{dx}\ =\ r_n\,y$$ or $$\frac{P_{k+1}}{P_k}\ =\ r_n$$

and so is of the form:

$$y\ =\ \sum_{n\,=\,1}^m\,C_n\,e^{r_nx}$$ or $$P_k\ =\ \sum_{n\,=\,1}^m\,C_n\,(r_n)^k$$

For a pair of complex roots (they always come in conjugate pairs) $p\ \pm\ iq$ or $r\,e^{\pm is}$, a pair of $$C_ne^{r_nx}$$ or $C_n\,(r_n)^k$may be replaced by $$e^{px}(A\,cos(qx)\,+\,iB\,sin(qx))$$ or $$r^k(A\,cos(sk)\,+\,iB\,sin(sk))$$

However, if the polynomial has some repeated roots:

$$\prod_{p\,=\,1}^q\prod_{n\,=\,1}^p(D\,-\,r_n)^p\,y\ =\ 0$$ or $$\prod_{p\,=\,1}^q\prod_{n\,=\,1}^p(x\,-\,r_n)^p\ =\ 0$$

then the general solution is of the form:

$$y\ =\ \sum_{p\,=\,1}^q\sum_{n\,=\,1}^pC_{n,p}\,x^{p-1}\,e^{r_nx}$$ or $$P_k\ =\ \sum_{p\,=\,1}^q\sum_{n\,=\,1}^pC_{n,p}\,n^{p-1}\,(r_n)^k$$

* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!

 

[fresh_42]

Recurrences are subject to an entire branch of mathematics, of course one which directly connects to algorithm theory in computer science as well as automaton theory and the theory of formal languages.