Results 1 to 2 of 2

Math Help - Mixed Recurrence Relation

  1. #1
    Newbie
    Joined
    Mar 2008
    Posts
    12

    Mixed Recurrence Relation

    We have the original Fibonacci sequence 1,1,2,3,5,8,13,..., and we form another sequence by writing each term twice. That is, we get 1,1,1,1,2,2,3,3,... as our final sequence. How can we find a linear,const coeff., homogeneous recurrence relation which is satisfied by this sequence?

    Okay, let g(x) denote the generating function of the original Fibonacci sequence. We know that

    g(x) = 1 + x + 2*x^2 + 3*x^3 + ... . Multiplying by x, we get
    x*g(x) = x + x^2 + 2*x^3 + ... . Multiplying by x again, we obtain
    (x^2)*g(x) = x^2 + x^3 + ... . Then we find that

    g(x)[x^2 - x - 1] = 1 => g(x) = 1 / (x^2 - x - 1). The final sequence has the generating function h(x) = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 3*x^6 + ... . The question is : how to find a useful closed expression for h(x)?(i guess by decimation, but how?) Thanks
    Last edited by hastings; March 15th 2008 at 09:02 AM. Reason: adding a word
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by hastings View Post
    We have the original Fibonacci sequence 1,1,2,3,5,8,13,..., and we form another sequence by writing each term twice. That is, we get 1,1,1,1,2,2,3,3,... as our final sequence. How can we find a linear,const coeff., homogeneous recurrence relation which is satisfied by this sequence?

    Okay, let g(x) denote the generating function of the original Fibonacci sequence. We know that

    g(x) = 1 + x + 2*x^2 + 3*x^3 + ... . Multiplying by x, we get
    x*g(x) = x + x^2 + 2*x^3 + ... . Multiplying by x again, we obtain
    (x^2)*g(x) = x^2 + x^3 + ... . Then we find that

    g(x)[x^2 - x - 1] = 1 => g(x) = 1 / (x^2 - x - 1). The final sequence has the generating function h(x) = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 3*x^6 + ... . The question is : how to find a useful closed expression for h(x)?(i guess by decimation, but how?) Thanks
    x_n=x_{n-2}+x_{n-4}

    with x_1=x_2=x_3=x_4=1

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. big o recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 4th 2011, 03:49 AM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 02:15 AM
  3. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 17th 2010, 01:52 AM
  4. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 2nd 2007, 11:14 PM
  5. Recurrence Relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 19th 2007, 06:54 PM

Search Tags


/mathhelpforum @mathhelpforum