Fibonacci

An algebraic approach


Consider the set Z of infinite real sequences (a₁, a₂, a₃, ... ) which satisfy the recursive relation
a_n+2 = a_n+1 + a_n .
Because of the linearity of the recursion we can define in Z addition and scalar multiplication by
(a₁, a₂, a₃, ... ) + (b₁, b₂, b₃, ... ) = (a₁+b₁, a₂+b₂, a₃+b₃, ... ) and
c.(a₁, a₂, a₃, ... ) = (c.a₁, c.a₂, c.a₃, ... ).
The set Z with the defined addition and scalar multiplication is a linear space (vector space).
If the first two elements a₁ and a₂ of a sequence (a₁, a₂, a₃, ... ) are known, we may find every element of the sequence with the help of the recursive relation.
It is obvious that {(1,0,...), (0,1,...)} is a base of the linear space Z.
Another, more often used base is {(1,1,...),(1,3,...)}. The first base element is called the sequence of Fibonacci and the second the sequence of Lucas.
Another interesting base is {(1,r,...), (1,s,...)} with
r = (1 + sqrt(5))/2 en s = (1 - sqrt(5))/2. As 1 + r = r² is r + r² = r³ etc. and so (1,r,...) is a geometric sequence: (1, r, r², r³, r⁴, r⁵, ... )
In the same way we may show that (1,s,...) is a geometric sequence.
The sequences of Fibonacci and Lucas may be represented with regard to the last mentioned base.
This yields for the n^th Fibonacci number F_n = (rⁿ - sⁿ) / (r - s) and for the n^th Lucas number L_n = rⁿ + sⁿ.