Fibonacci

Ein algebraisches Verfahren


Wir betrachten die Menge Z der unendlichen reellen Zahlenfolgen (a₁, a₂, a₃, ... ) die der Vorschrift a_n+2 = a_n+1 + a_n erfüllen.
Wegen der Linearität der Vorschrift können wir innerhalb dieser Menge Z eine Addition und eine skalare Multiplikation definieren durch
(a₁, a₂, a₃, ... ) + (b₁, b₂, b₃, ... ) = (a₁+b₁, a₂+b₂, a₃+b₃, ... ) und
c.(a₁, a₂, a₃, ... ) = (c.a₁, c.a₂, c.a₃, ... ).
Damit wird Z ein linearer Raum.
Wenn wir von einer Zahlenfolge (a₁, a₂, a₃, ... ) die Anfangswerte a₁ und a₂ kennen, dann können wir mit Hilfe der Rekursionsvorschrift jedes FolgenGlied berechnen. Es ist nun klar dass {(1,0,...), (0,1,...)} eine Basis ist für diesen linearen Raum.
Eine andere, viel öfters benutzte Basis ist {(1,1,...),(1,3,...)}. Das erste Basiselement wird die Fibonaccifolge genannt und das zweite die Lucasfolge. Eine andere interessante Basis ist {(1,r,...), (1,s,...)} mit
r = (1 + sqrt(5))/2 und s = (1 - sqrt(5))/2. Da 1 + r = r² gilt auch r + r² = r³ usw. Also bildet (1,r,...) eine geometrische Zahlenfolge (1, r, r², r³, r⁴, r⁵, ... )
Analog bildet (1,s,...) eine geometrische Zahlenfolge.
Die Fibonaccifolge und die Lucasfolge können wir bezüglich der letzterwähnten Basis representieren.
Wir erhalten also für die n-te Fibonaccizahl F_n = (rⁿ - sⁿ) / (r - s) und für die n-te Lucaszahl L_n = rⁿ + sⁿ.