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!

Homework Help: Recurrence relations

  1. Apr 1, 2015 #1
    1. The problem statement, all variables and given/known data:
    I am just learning recurrence relations, and they are proving challenging.

    2. Relevant equations -- Let's have xn = 3xn-1 + 6xn-2.
    I wanted to look at it with two scenarios. The first is x0 = 1 and x1 = 3. The second is x1=3 and x2 = 4

    3. The attempt at a solution
    Is there a difference between having a staring point of x0and x1? That is the sticking point.

    As far as the solution is concerned, if I wanted to go to the 5th term, I can do the x1=3 and x2 = 4 scenario -- x1 = 1, x2 = 4, x3 = x3=30, x4 = 114, and x5= 522.

    The scenario with x0 is challenging to me. How can you have a recurrence relation where the n-1 term leaves you a negative number? How do you know where to start? Is it understood that, in the equation that is above, I would start with 3(x0(or 3 * 1) + 6(x1(6 * 3), with a sum of 21?

    Also, how would you turn this into a formula? How do you determine the degree? For this last question, I just need a point in the right direction, I'm not asking for someone to do the questions for me.
  2. jcsd
  3. Apr 1, 2015 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The usual way of writing these things is as ##x_n = 3 x_{n-1} + 6x_{n-2} \; \text{for} \; \; n \geq 2##, with ##x_0=1, x_1 = 3##. In other words, the recursion does not apply when ##n = 0, 1##.

    If you wanted a formula you could try ##x_n = r^n## for some ##r##. Then, the recursion would give ##r^n = 3 r^{n-1}+ 6 r^{n-2}##, or ##r^2 = 3 r + 6##. This is a quadratic, and so has two roots, usually---in this case it does have two real roots. So, the general solution would be of the form
    [tex] x_n = A r_1^n + B r_2^n, \; n \geq 2 [/tex]
    where ##r_1, r_2## are the two roots. We can find values of ##A, B## either by (i) requiring that this expression hold as well for ##n = 0,1##; or (ii) computing ##x_2, x_3## from the recursion as well as from the above formula, giviing two equations for ##A,B##.
  4. Apr 1, 2015 #3
    Thank you, this is something to speak about w/ the prof, it is still not sinking in.
  5. Apr 1, 2015 #4


    User Avatar
    Homework Helper

    In some cases, you can solve for negative n using the same recurrence relation. Given [itex]x_{n}[/itex] and [itex]x_{n-1}[/itex], you can solve for [itex]x_{n-2}[/itex]:
    x_n = 3x_{n-1} + 6x_{n-2} \\
    x_{n-2} = (x_n - 3x_{n-1}) / 6 \\
    x_1 = 3 \\
    x_0 = 0 \\
    x_{-1} = 1/2 \\
    x_{-2} = -1/4 \\
    x_{-3} = 5/24 \\
    x_{-4} = -7/48 \\
    x_{-5} = 31/288 \\
    Last edited: Apr 2, 2015
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted