Results 1 to 5 of 5

Math Help - Second order recurrence relations

  1. #1
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Second order recurrence relations

    Hello!
    New here.

    I'm stuck on a proof from a textbook called Discrete Mathematics by Epp.

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

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

    Using n = 2, you end up with the quadratic t^{2} - At - B = 0, 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 [ a_{n} = Aa_{n-1} + Ba_{n-2}]?"

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

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


    Any help appreciated.
    Last edited by CaptainBlack; October 15th 2011 at 04:02 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Second order recurrence relations

    Quote Originally Posted by hachataltoolimhakova View Post
    Hello!
    New here.

    I'm stuck on a proof from a textbook called Discrete Mathematics by Epp.

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

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

    Using n = 2, you end up with the quadratic t^{2}  At - B = 0, 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 [ a_{n} = Aa_{n-1} + Ba_{n-2}]?"

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

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


    Any help appreciated.
    The point is it demonstrates where the characteristic equation comes from. Seeing this you should be able to use the same technique to find the characteristic equation in other situations.

    Also many people do not like it if a book or teacher pulls things out of the air and then demonstrates that they solve the problem at hand.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Re: Second order recurrence relations

    Thanks for the response CB.
    Couldn't you make the same argument about the first part? It says "suppose" that a sequence 1, t, t^{2},... satisfies the recurrence relation. But why? Why should I "suppose" such a sequence satisfies the recurrence relation? This is only demonstrated, from my understanding, after the quadratic has been multiplied by t^{n-2}. I do not know why I should make the supposition that the sequence satisfies the recurrence relation, where did it come from? I can at least see, a posteriori, that multiplying the quadratic by t^{n-2} yield the recurrence relation; and you can therefore, having established this, see that the values of t are the roots of the quadratic. It just seems that to arrive at the conclusion would be more likely by starting with the quadratic and observing that multiplying it by t^{n-2} yields a recurrence relation of the form at^n-1 = bt^n-2 = t^n.

    Thanks again CB.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Angry Re: Second order recurrence relations

    Quote Originally Posted by hachataltoolimhakova View Post
    Thanks for the response CB.
    Couldn't you make the same argument about the first part? It says "suppose" that a sequence 1, t, t^{2},... satisfies the recurrence relation. But why? Why should I "suppose" such a sequence satisfies the recurrence relation?
    One reason for supposing this is by observation of numerical and other experiments, and another is by analogy from the equivalent differential equations.

    The secret that you may never discover in a maths course is that maths uses a lot of experiments (and analogy) to give clues about what direction to pursue in discovering results.

    Conjectures are often the left over experimental/analogical results that no one has yet been able to prove or disprove.

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2011
    Posts
    7

    Re: Second order recurrence relations

    Thanks CB!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 08:56 PM
  2. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 10th 2008, 10:21 AM
  3. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 9th 2008, 12:33 PM
  4. help with recurrence relations
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 11th 2008, 06:07 PM
  5. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 19th 2008, 09:06 PM

Search Tags


/mathhelpforum @mathhelpforum