Eisenstein-Fibonacci sequences

[Max A.]

On 11/2/06, Max A. <maxale at gmail.com> wrote:

> >  Let b(0) = w, b(1) = w^2, b(n) = w*b(n-1) + b(n-2),
> >  where w = omega = (-1 + i*sqrt(3))/2 and w^2 = omega^2
> >  = (-1 - i*sqrt(3))/2.
>
> First off, using the identity w^2 = -w-1, we can uniquely represent
> b(n) as u(n)+v(n)*w where u(n) and v(n) are integers.

[...]

> u(n) and v(n) satisfies the recurrence
> u(n) = - u(n-1) + u(n-2) + u(n-3) - u(n-4)
> v(n) = - v(n-1) + v(n-2) + v(n-3) - v(n-4)
> with u(0)=0, u(1)=-1, u(2)=1, u(3)=-2
> and v(0)=1, v(1)=-1, v(2)=1, v(3)=-1.

o.g.f. for u(n) is
-x/(1 + x - x^2 - x^3 + x^4)
and
o.g.f. for v(n) is
(1-x^2)/(1 + x - x^2 - x^3 + x^4)

Hence, o.g.f. for b(n) is
(-x + w*(1-x^2)) / (1 + x - x^2 - x^3 + x^4)

Max