- #1
- 19,532
- 10,254
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!
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!