How are recurrence relations used in mathematics and computer science?

In summary, a recurrence relation is an equation that defines a sequence by using preceding terms. The most well-known examples are the Fibonacci numbers and binomial coefficients. Ordinary differential equations can also be considered as recurrence relations and can be solved using the characteristic polynomial method. The general solution for a polynomial with distinct roots involves a linear combination of solutions, while repeated roots result in a more complex form. Recurrences are an important concept in mathematics, particularly in the fields of algorithm theory and formal languages.
  • #1
19,464
10,078
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:

[tex]F_n\ =\ F_{n-1}\ +\ F_{n-2}[/tex]

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:

[tex]\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)[/tex]

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:

[tex]\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[/tex]

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

[tex]\sum_{n\,=\,0}^m\,a_{k+n}\,P_{k+n}\ =\ 0\ \mapsto\ \sum_{n\,=\,0}^m\,a_n\,x^n\ =\ 0[/tex]

If this polynomial has distinct (different) roots [itex]r_1,\dots,r_m[/itex]:

[tex]\prod_{n\,=\,1}^m(D\,-\,r_n)\ =\ 0[/tex] or [tex]\prod_{n\,=\,1}^m(x\,-\,r_n)\ =\ 0[/tex]

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

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

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

and so is of the form:

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

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

However, if the polynomial has some repeated roots:

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

then the general solution is of the form:

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

* 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!
 
Mathematics news on Phys.org
  • #2
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.
 

Related to How are recurrence relations used in mathematics and computer science?

What is a recurrence relation?

A recurrence relation is a mathematical equation that defines a sequence of numbers by relating each term to previous terms in the sequence. It is a way of expressing a pattern or relationship between numbers in a systematic way.

How is a recurrence relation different from a regular mathematical equation?

A recurrence relation involves a recursive relationship, meaning that the value of a term in the sequence is dependent on previous terms in the sequence. This is different from a regular equation where each term is independent of the others.

What are some real-life examples of recurrence relations?

Recurrence relations can be found in various fields, such as chemistry, physics, and computer science. Some examples include the Fibonacci sequence in nature, the Tower of Hanoi puzzle, and the algorithm used for calculating the shortest path in a network.

Why are recurrence relations useful?

Recurrence relations can be used to solve problems that involve repeated operations or patterns. They also allow for the efficient representation and computation of complex sequences.

How can I solve a recurrence relation?

There are several methods for solving a recurrence relation, such as substitution, iteration, and generating functions. The appropriate method to use depends on the specific recurrence relation and its complexity.

Similar threads

Replies
1
Views
758
  • General Math
Replies
1
Views
1K
  • General Math
Replies
3
Views
895
Replies
3
Views
959
Replies
3
Views
1K
Replies
5
Views
752
Replies
6
Views
1K
Replies
1
Views
2K
Replies
8
Views
1K
  • Advanced Physics Homework Help
Replies
1
Views
1K
Back
Top