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