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: Second Order Homogeneous Recurrence Relation

  1. Oct 13, 2011 #1

    I was reading the proof (I think it constitutes a proof) for second order homogeneous recursive relations from the book Discrete Mathematics with Applications by S. Epp, and it seems, to me at least, to be excessive; which suggests that I don’t understand the proof.

    It goes something like the following (the proof is here: http://books.google.co.uk/books?id=...er homogeneous recurrence relations&f=false):

    Firstly, there is the recurrence relation [itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex], then the book states that “uppose that for some number t… the sequence 1, t^{1}, t^{2}, t^{3},…,t^{n},….
    satisfies [[itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex]].”

    This means that [itex]t^{n} = At^{n-1} + Bt^{n-2}[/itex].

    Using n = 2, you end up with the quadratic [itex]t^{2} – At – B = 0[/itex], from which you can derive the values for t (the roots of the quadratic).

    The book then states: “Now work backward. Suppose t is any number that satisfies [the quadratic]. Does the sequence 1, t^{1}, t^{2}, t^{3},…,t^{n},…. satisfy [[itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex]]?”

    To answer this, Epp multiplies the quadratic by [itex]t^{n-2}[/itex].

    Here’s my issue: I don’t understand the point of the first part. Why not just start with the quadratic and multiply by [itex]t^{n-2}[/itex]? This shows that the sequence [itex]1, t^{1}, t^{2}, t^{3},…,t^{n},….[/itex] satisfies [itex]a_{n} = Aa_{n-1} + Ba_{n-2}[/itex] (since [itex]t^{n} = At^{n-1} + Bt^{n-2}[/itex] is derived from the quadratic by multiplying by [itex]t^{n-2}[/itex]) when t is equal to the roots of the quadratic. Why suppose that there is a sequence 1, t, t2,… that satisfies the recurrence relation then work towards the quadratic formula? I don’t see what it demonstrates? Why not just start with the quadratic and show such a relation exists, and work from there?

    Any help appreciated.
  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