Results 1 to 3 of 3

Math Help - Recurrence relation

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    12

    Recurrence relation

    The sequence {a_n} = 1,11,41,131,401,... satisfies the relation
    a_(n+2) = 4*a_(n+1) - 3*a_n for n>=0. Find a const. coefficient, linear, homogeneous recurrence relation(of smallest order) which is satisfied by the sequence
    (1)^2,,(11)^2,(41)^2,(131)^2,... = 1,121,1681,17161,... .

    The characteristic equation for the given relation is x^2 - 4*x + 3 = 0. The roots for this equation are 3 and 1. Imposing the values of a_0 and a_1, we find that a_n = 5*(3^n) - 4. Here is the point i don't know what to do next.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by hastings View Post
    The sequence {a_n} = 1,11,41,131,401,... satisfies the relation
    a_(n+2) = 4*a_(n+1) - 3*a_n for n>=0. Find a const. coefficient, linear, homogeneous recurrence relation(of smallest order) which is satisfied by the sequence
    (1)^2,,(11)^2,(41)^2,(131)^2,... = 1,121,1681,17161,... .

    The characteristic equation for the given relation is x^2 - 4*x + 3 = 0. The roots for this equation are 3 and 1. Imposing the values of a_0 and a_1, we find that a_n = 5*(3^n) - 4. Here is the point i don't know what to do next.
    If a_n = 5\times3^n - 4 then a_n^2 = 25\times 9^n - 20\times3^n + 16. Now suppose that a_{n+3}^2 = pa_{n+2}^2 + qa_{n+1}^2 + ra_n^2. Since
    a_{n+3}^2 = 25\times 9^{n+3} - 20\times3^{n+3} + 16,
    a_{n+2}^2 = 25\times 9^{n+2} - 20\times3^{n+2} + 16 and
    a_{n+1}^2 = 25\times 9^{n+1} - 20\times3^{n+1} + 16,
    we can compare coefficients of 9^n, 3^n and the constant terms, in the equation a_{n+3}^2 = pa_{n+2}^2 + qa_{n+1}^2 + ra_n^2. This gives a set of linear equations for p, q and r, namely
    81p+9q+r=729,
    9p+3q+r=27,
    p+q+r=1.

    If I haven't made a careless mistake, the solution to these equations gives the result a_{n+3}^2 = 13a_{n+2}^2 - 39a_{n+1}^2 + 27a_n^2. This is certainly a constant coefficient, linear, homogeneous recurrence relation which is satisfied by the given sequence. BUT I'm not sure whether it is the one of smallest order. (I guess that it must be.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2008
    Posts
    12
    Thanks Opalg. I went through all the steps you proceeded, and found the same result. Assuming a third order recurrence relation was clever and i'm convinced that this is of smallest possible order because i imitated the same result for a second order relation but didn't come up with a reasonable answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 16th 2011, 12:27 AM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 03:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 02:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 07:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 09:02 AM

Search Tags


/mathhelpforum @mathhelpforum