1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is a recurrence relation

  1. Jul 23, 2014 #1
    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!
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted