Results 1 to 7 of 7

Math Help - Recurrence relations

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    41

    Recurrence relations

    If I have a recurrence relation such as:
    a(n) = A*a(n-1) + B*a(n-2) where a(0)=X,  a(1)=Y
    how do I solve this?

    Wikipedia explains how to solve such an equation and I used it and it worked for me. But I don't understand how it works.

    This is what Wiki says (in short):

    With our equation above we try to find an answer of the form a(n) = r^n
    Then r^n=A*r^(n-1)+B*r^(n-2)
    Then r^2-(A*r)-B=0
    You solve this and you write: a(n)=C*root1^n+D*root2^n
    You then work out what C and D are (using a(0) and a(1) which you already know and you have your equation.
    (This is the link to wikipedia's explanation:
    Recurrence relation - Wikipedia, the free encyclopedia)

    Could someone explain why this works please.
    And also, how does one prove that the new formula is correct?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2010
    Posts
    41
    I worked out a proof by induction for my specific problem. I still don't understand how I got the equation though. Can anyone explain it?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    The 'charachteristic equation' associated to the homogeneous linear recurrence relation a_{n}= A\ a_{n-1} + B\ a_{n-2} is...

    r^{2} -A\ r - B = 0 (1)

    If the (1) has two distinct real roots r_{1} and r_{2} the solution is...

    a(n)= c_{1}\ r_{1}^{n} + c_{2}\ r_{2}^{n} (2)

    ... where the constants c_{1} and c_{2} are derived from the 'initial conditions'...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2010
    Posts
    41
    Thanks for your help but I still don't understand why it works. All I understand is that it does work.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    A second order linear homogeneous recurrence relation has the form...

    \displaystyle x_{n+2} + a_{1}\ x_{n+1} + a_{2}\ x_{n}=0 (1)

    a) we first demonstrate that if u_{n} and v_{n} are two independent solution of (1), then also c_{1}\ u_{n} + c_{2}\ v_{n}, where c_{1} and c_{2} are arbitrary constants, is also solution of (1)...

    ... for what we have supposed is...

    \displaystyle u_{n+2} + a_{1}\ u_{n+1} + a_{2}\ u_{n}=0

    \displaystyle v_{n+2} + a_{1}\ v_{n+1} + a_{2}\ v_{n}=0 (2)

    ... so that multiplying the first of (2) by c_{1} and the second of (2) by c_{2} we obtain...

    \displaystyle c_{1}\ u_{n+2} + c_{2}\ u_{n+2} + a_{1}\ (c_{1} \ u_{n+1} + c_{2}\ v_{n+1}) + a_{2}\ (c_{1}\ u_{n} + c_{2}\ v_{n}) =0 (3)

    ... that is what we want to demonstrate...

    b) ... then we demonstrate that if a_{1} and a_{2} are constant and r_{1} and r_{2} are two real dinstict roots of the equation...

    \displaystyle r^{2} + a_{1}\ r + a_{2} =0 (4)

    ... then u_{n}= r_{1}^{n} and v_{n}= r_{2}^{n}...

    ... setting u_{n}= r_{1}^{n} is the first of (3) we obtain...

    \displaystyle u_{n+2} + a_{1}\ u_{n+1} + a_{2}\ u_{n} = r_{1}^{n}\ (r_{1}^{2} + a_{1}\ r_{1} + a_{2}) =0 (5)

    ... that is what we want to demonstrate. The same is for v_{n}...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2010
    Posts
    41
    Thank you
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,862
    Thanks
    743
    Hello, durrrrrrrr!

    I'll explain the steps.
    I don't know if it will clear up the mystery for you.


    \text{If I have a recurrence relation such as:}

    a(n) \:=\: A\!\cdot\!a(n-1) + B\!\cdot\!a(n-2)\,\text{ where }a(0)=X,\:a(1)=Y

    \text{how do I solve this?}

    First, we conjecture that the generating function is exponential.
    . . Let a(n) \:=\:r^n

    So we have: . r^n \:=\:A\!\cdot\!r^{n-1} +B\!\cdot\!r^{n-2} \quad\Rightarrow\quad r^n - A\!\cdot\!r^{n-1} - B\!\cdot\!r^{n-2} \:=\:0

    Divide by r^{n-2}\!:\;\;r^2 - Ar - B \:=\:0

    Quadratic Formula: . r \;=\;\dfrac{A \pm\sqrt{A^2 + 4B}}{2}


    Form a linear combination of the two roots:

    . . a(n) \;=\;C\left(\dfrac{A + \sqrt{A^2+4B}}{2}\right)^n + D\left(\dfrac{A - \sqrt{A^2 + 4B}}{2}\right)^n .[1]


    Use the first two terms of the sequence to set up a system of equations:

    . . \begin{array}{ccccccc}<br />
a(0) = X\!: & C \qquad + \qquad D &=& X \\<br />
a(1) = Y\!: & C\left(\frac{A + \sqrt{A^2 + 4b}}{2}\right) + D\left(\frac{A - \sqrt{A^2+4B}}{2}\right) &=& Y \end{array}


    Solve the system: . \begin{Bmatrix}<br />
C &=& \dfrac{2Y - X(A - \sqrt{A^2 + 4B}\,)}{2\sqrt{A^2+4B}} \\ \\[-3mm]<br /> <br />
D &=& \dfrac{X(A + \sqrt{A^2+4B}\,) - 2Y}{2\sqrt{A^2+4B^2}} <br />
\end{Bmatrix}


    Substitute into [1] and we have the closed form of the recurrence.

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 7th 2009, 05:14 PM
  2. recurrence relations...
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 4th 2009, 11:54 PM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  4. recurrence relations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 19th 2008, 10:08 PM
  5. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 11th 2008, 12:57 AM

Search Tags


/mathhelpforum @mathhelpforum