The Universe of Disco

Fibonacci-like sequences

John T. Guthrie:

I can hand you two complex numbers, a and b. If I tell you that for the sequence G(k), G(m)=a, and G(n)=b, and G(k)=G(k-1)+G(k-2), then you can compute the rest of the sequence G(k) for all integers k.

let's call such sequences "Fibonacci-like".

Since the set of Fibonacci-like sequences is closed under addition and under multiplication of each element by a constant, the set of such sequences forms a vector space of dimension 2.

Abbreviate such a sequence by writing (G(0), G(1)), which as you pointed out is sufficient to determine the whole thing. With this abbreviation, the standard Fibonacci sequence is just (0, 1).

(0, 1) and (1, 0) are a basis for the vector space. But (1, 0) is nothing more than the Fibonacci sequence shifted over by one element; it's (F(-1), F(0)).

Thus any Fibonacci-like sequence G satisfies:

G(n) = G(1) F(n) + G(0) F(n-1)

(*)

In particular, consider the shifted Fibonacci sequence S_k(n) = F(n+k). Then (*) reduces to:

F(n+k) = F(k+1) F(n) + F(k) F(n-1)

which I think is a simpler proof of this identity than the obvious inductive proof.

All sorts of other identities fall out of special cases of (*). For example, the Lucas sequence 1, 3, 4, 7, 11, ... is Fibonacci-like with has L(0) = 1, L(1) = 3. By (*):

L(n) = 3F(n) + F(n-1)

or if you prefer:

L(n) = 2F(n) + F(n+1)

and of course a change of basis for the vector space produces a version of (*) that allows one to write any Fibonacci-like sequence in terms of the Lucas sequence.

(Very easy exercise: The Lucas sequence contains no multiples of 5. Slightly harder: For which n does the Fibonacci sequence contain no multiples of n?)

[Other articles in category /math] permanent link