1. Not finding help here? Sign up for a free 30min 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!

Recurrence Relation to Non-recursive Formula

  1. Jun 14, 2010 #1
    1. The problem statement, all variables and given/known data

    The sequence [tex]f_n[/tex] is defined by [tex]f_0=f_1=2[/tex] and

    [tex]f_n = (\frac{f_{n-1}+2f_{n-2}}{6})[/tex], when [tex]n\geq2[/tex].

    Find a non-recursive formula for [tex]f_n[/tex]

    3. The attempt at a solution

    Well I have solved for the closed formula of the generating function which I will call g(x) so

    [tex]
    g(x) = \frac{12-10x}{6-x-2x^2}
    [/tex]

    My question is, is this what they are looking for or do I need to continue and use partial fractions and linear algebra to get farther?
     
  2. jcsd
  3. Jun 14, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    They want to find a general formula for f_n. I think you want to find two solutions of the form (p1)^n and (p2)^n to your recursion relation and then combine them as c1*(p1)^n+c2*(p2)^n and solve for c1 and c2 to fit the initial conditions.
     
  4. Jun 14, 2010 #3
    Well I used Partial fractions and then linear algebra and got

    [tex]
    c_1 = \frac{-6}{7}
    [/tex]

    [tex]
    c_2 = \frac{32}{7}
    [/tex]

    So where would I have to go from there
     
  5. Jun 14, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I have no idea what you're doing unless you show what you are doing. I really don't think partial fractions or linear algebra have much to do with it. There are two exponential solutions to the linear recursion relation. I.e. of the form p^n. What are the p's? Use 'quadratic equation'.
     
  6. Jun 14, 2010 #5
    You lost me, what is the linear recursion relation (I am not huge on this terminology) That might also explain these p^n's you are talking about....
     
  7. Jun 14, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Put f_n=p^n into the recurrence relation. You'll get a quadratic equation in p after you cancel some powers. Just try it. Since the equation in linear in f, linear combinations of those two solutions are also solutions. This is an awful lot like a linear second order ODE.
     
  8. Jun 14, 2010 #7
    The recurrence relation is the original formula I had? And if I put p^n in place of f_n the what would f_n-1 become?
     
  9. Jun 14, 2010 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    f_n-1 becomes p^(n-1) doesn't it?
     
  10. Jun 14, 2010 #9
    Ok so then my equation would be

    [tex]
    6p^n -p^{n-1} - 2p^{n-2} = 0
    [/tex]

    so using the quadratic equation I get that

    [tex]
    p = \frac{1 \pm \sqrt{27}}{12}
    [/tex]

    then what?
     
  11. Jun 15, 2010 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Which quadratic did you solve to get those roots?? That's not what I get. Once you've got the correct roots, it's just what I said. Your solution is a linear combination of powers of the two roots. Solve for c1 and c2.
     
  12. Jun 15, 2010 #11
    If we put a p^n in for all f's we get

    [tex]
    p^n = (\frac{p^{n-1}+2p^{n-2}}{6})
    [/tex]

    so multiplying both sides by six to get rid of the fraction and setting it equal to zero we get

    [tex]
    6p^n -p^{n-1} - 2p^{n-2} = 0
    [/tex]

    which is the quadratic I solved. Unless a = -2, b=-1 and c=6. I did it the opposite way around where a=6, b=-1, and c=-2. Is that my mistake?
     
  13. Jun 15, 2010 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    b^2-4ac=1-(4*6*(-2))=49. There's no 'sqrt(27)' around. Even if you understand the problem perfectly, you'll never get the answer unless you take some care.
     
  14. Jun 15, 2010 #13
    I know, I was doing this really late at night but now I get that my roots are equal to

    [tex]
    \frac{2}{3}, \frac{-1}{2}
    [/tex]

    I know you have said from there that they are a linear combination of powers of the two roots and I can solve it that way, but I do not know what a linear combination of powers is?
     
  15. Jun 15, 2010 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    (2/3)^n and (-1/2)^n solve your recurrence relation. So put f_n=c1*(2/3)^n+c2*(-1/2)^n. Solve for the constants c1 and c2.
     
  16. Jun 15, 2010 #15
    Ok, to solve for c1 and c2 though I would need two equations. Does that mean I need to use the fact that f_0=f_1=2 somehow?
     
  17. Jun 15, 2010 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes.
     
  18. Jun 15, 2010 #17
    Oh, my two equations would be the following correct?

    [tex]
    2=c_1\left(\frac{2}{3}\right)^0 + c_2\left(\frac{-1}{2}\right)^0
    [/tex]

    and

    [tex]
    2=c_1\left(\frac{2}{3}\right)^1 + c_2\left(\frac{-1}{2}\right)^1
    [/tex]
     
  19. Jun 15, 2010 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Of course they would.
     
  20. Jun 15, 2010 #19
    So

    [tex]
    c_1 = \frac{18}{7}
    [/tex]

    [tex]
    c_2 = \frac{-4}{7}
    [/tex]

    so what do those get put into to find the non-recursive formula for f_n ?
     
  21. Jun 15, 2010 #20

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    A nonrecursive formula for f_n is a formula you can plug into your calculator to find f_n without first finding f_n-1 and f_n-2. What do we now have that might be such a formula?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook