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: SAT/ GCSE-Level Recurrence Relation Problem

  1. Jul 16, 2011 #1
    1. The problem statement, all variables and given/known data
    Hi! This is my first time on the site. I look forward to working with everyone…but hopefully not too much, assuming I‘m learning things correctly. :P

    My question pertains to Recurrence Relations, so here it goes…

    Foreword: The text book I’m using actually supplies the answer to the question, so I already have a point of reference, but my attempt does not match up with the answers. I believe my approach is essentially correct, as it has yielded the correct answers for a similar question beforehand. Answer is: 1, 3, 7, 17, 41

    Please note that I am beginning the question from u3, as we already have the values for u1 and u2.

    2. Relevant equations

    Q. Find the first five terms of the sequence:

    u1 = 1, u2 = 3 and un = 2un-1 + un-2

    3. The attempt at a solution


    Solve un+1 where un = 3un-1 - un-2
    => 3u(n+1)-1 - u(n+1)-2

    Begin by substituting 3 (i.e. u2) for un:
    If n = 1 then u3 = 2((3+1) - 1) + ((3+1) -2) => 2(4-1) + (4-2) => 6 + 2
    Ans.: u3 = 8... but should be 7!!!

    Proceeding with u3 as 7, not 8...

    If n = 2 then u4 = 2((7+1) -1) + ((7+1) -2) => 2(8-1) + (8-2) => 14 + 6
    Ans.: u4 = 20... But should be 17!!!

    Note, I am omitting solution of u5 for brevity’s sake.

    I‘m sure the answer is staring me in the face, but I just can’t seem to figure it out!
    Can anyone help?

    Last edited: Jul 16, 2011
  2. jcsd
  3. Jul 16, 2011 #2


    User Avatar
    Homework Helper

    Not too sure what you're going here but let's calculate [itex]u_{3}[/itex] from the recurrence relation.
    u_{3}=2u_{2}+u_{1}=2\times 3+1=7
    Working for [itex]u_{4}[/itex]
    u_{4}=2u_{3}+u_{2}=2\times 7+3=17
  4. Jul 16, 2011 #3
    Woah, that was easier than I was making it! Thank you.

    One final question though, why is the value of u1 subbed into un-2 and u2 into un-1?
  5. Jul 16, 2011 #4


    User Avatar
    Homework Helper

    you're finding n=3, so n-1=2 and n-2=1.
  6. Jul 16, 2011 #5
    Thank you very much. You've really helped me out!
  7. Jul 16, 2011 #6


    User Avatar
    Homework Helper

    it's why I help here.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook