Thread: 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

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

with

RonL