# Mixed Recurrence Relation

• Mar 15th 2008, 08:23 AM
hastings
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
• Mar 16th 2008, 04:45 AM
CaptainBlack
Quote:

Originally Posted by hastings
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