2 Grundlegendes

2.1 Formale Definitionen

Wenn wir im folgenden die allgemeine Fibonaccifolge (f_n)_{n $\in$ $\mathbb {N}$} betrachten, so schreiben wir einfach exemplarisch und ein wenig unsauber f_n (je nach Kontext kann f_n natürlich auch den Folgenwert selbst bezeichnen!) oder manchmal in Funktionsschreibweise f (für f : $\mathbb {\: N}$ $\rightarrow$ $\mathbb {N}$,  n $\mapsto$ f_n). Wir setzen dabei voraus, daß zwei nicht näher spezifizierte Folgenglieder f₀ $\in$ $\mathbb {N}$ und f₁ $\in$ $\mathbb {N}$ $\setminus$ $\left\{\vphantom{ 0}\right.$ 0$\left.\vphantom{ 0}\right\}$ sowie die Rekursionsgleichung f_n : = f_n-1 + f_n-2 diese Folge definieren. Der Fall f₁ = f₀ = 0 ergibt trivialerweise die konstante Folge f_n = 0, die wir in der folgenden Betrachtung ausklammern.

Für die Spezialfälle f₀ : = 0, f₁ : = 1 definieren die Folgenglieder f_n die spezielle bzw. eigentliche Fibonaccifolge, die wir mit (F_n)_{n $\in$ $\mathbb {N}$} oder kurz F_n, manchmal sogar in Funktionsschreibweise mit F bezeichnen wollen. Analog sei die Lucasfolge L_n für L₀ : = 2 und L₁ : = 1 definiert.

2.2 Einige Eigenschaften

In diesem Abschnitt folgen einige einfach zu beweisende Eigenschaften.

2.2.1 Gemeinsame Teiler

Haben zwei aufeinanderfolgende Glieder f_n sowie f_n+1 einen gemeinsamen Teiler, so gilt dies für alle Folgenglieder und insbesondere für f₀ und f₁. Dies leitet sich unmittelbar aus einem grundlegenden Satz der Zahlentheorie ab, da mit a $\equiv$ 0  ( mod t) und b $\equiv$ 0  ( mod t) auch a + b $\equiv$ a - b $\equiv$ 0  ( mod t) folgt (vgl. euklidischer Algorithmus zur Bestimmung des ggT). Im übrigen sei bemerkt, daß die natürliche Zahl 0 durch alle übrigen natürlichen Zahlen (mit Ausnahme der 0) ohne Rest teilbar ist.

2.2.2 Periodizität in Restklassen

2.2.2.1 Allgemeine Betrachtung

Betrachten wir f_n mod m: Da die Folgenwerte jeweils nur von der Summe ihrer beiden Vorgängerwerte abhängen und da f_n mod m lediglich m verschiedene Werte annehmen kann, müssen sich diese Werte periodisch wiederholen. Eine Periode ist gefunden, wenn wir zwei Wertepaare (f_r, f_r+1) und (f_s, f_s+1) mit r $\neq$ s gefunden haben, deren Reste modulo m gleich sind.

Da es höchstens m² viele paarweise verschiedene Wertepaare geben kann, garantiert uns diese grobe Abschätzung die Existenz einer Periode innerhalb des Intervalls $\left[\vphantom{0,m^{2}+1}\right.$0, m² + 1$\left.\vphantom{0,m^{2}+1}\right]$, da dieses Intervall m² + 1 viele Wertepaare enthält.

2.2.2.2 Beispiel

Betrachten wir die F_n sowie L_n modulo 8:

Table 5: Werte der Fibonacci- und Lucasfolge modulo 8

Table 5: Werte der Fibonacci- und Lucasfolge modulo 8

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13
Fn	0	1	1	2	3	5	0	5	5	2	7	1	0	1
Ln	2	1	3	4	7	3	2	5	7	4	3	7	2	1

Wir können erkennen, daß sich die Folgenwerte in beiden Fällen periodisch wiederholen müssen, da beide Folgenwerte jeweils nur von der Summe ihrer beiden Vorgängerwerte abhängen. Wenn zwei aufeinander folgende Werte mit zwei bereits vorher auftauchenden aufeinander folgenden Werten identisch sind, so haben wir eine Periode gefunden. Dies ist bei F_n für (F₁₂, F₁₃) $\equiv$ (F₀, F₁)  ( mod 8) und bei L_n für (L₁₂, L₁₃) $\equiv$ (L₀, L₁)  ( mod 8) der Fall. Das Angenehme bei Restklassenbetrachtungen ist, daß man prinzipiell nur endlich viele Fälle betrachten muß, um eine Eigenschaft zu beweisen.

2.2.2.3 Wir halten beispielhaft folgende Eigenschaften fest:

1. F_12n+$\Delta$ $\equiv$ F_$\Delta$  ( mod 8)
2. L_12n+$\Delta$ $\equiv$ L_$\Delta$  ( mod 8)
3. F_n $\equiv$ 0  ( mod 4) $\Rightarrow$ F_n $\equiv$ 0  ( mod 8) und n $\equiv$ 0  ( mod 6)
4. L_n $\neq$ 0  ( mod 8)

2.2.2.4 Die letzte Dezimalstelle

Als weiteres Beispiel können wir F_n bzw. L_n modulo 10 betrachten. Die Periode beträgt 60. Damit gilt:

1. F_n $\equiv$ F_{n mod 60}( mod 10)
2. L_n $\equiv$ L_{n mod 60} ( mod 10)

Durch die Betrachtung der relevanten Restklassen kann man vergleichsweise einfach auch Endziffern astronomisch großer Folgenwerte berechnen. Doch wer interessiert sich schon wirklich für die letzte Dezimalziffer von F_L1000 (=3) oder L_9⁹⁹ (=6)?

2.3 Negative Indices

Die allgemeine Fibonaccifolge läßt sich auf die ganzen Zahlen ausdehnen, indem wir überall die Gültigkeit der Gleichung f_n = f_n-1 + f_n-2 fordern. Damit gilt dann auch f_-n-1 + f_-n = f_-n+1 bzw. die äquivalente Form f_-(n+1) = f_-(n-1) - f_-n, die durch die induktive Definition f_-(n+1) : = f_-(n-1) - f_-n in Verbindung mit den »herkömmlichen« Startwerten f₀ und f₁ der Ursprungsfolge erfüllt wird.

Diese Erweiterung erlaubt es uns jedoch nicht, ungeprüft (und unbewiesen) alle Ergebnisse und Eigenschaften der Fibonaccifolge, die auf den natürlichen Zahlen definiert ist, auf die negativen Indices auszuweiten. Insbesondere treten nun negative Folgenwerte auf!

Table 7: Werte der erweiterten Fibonacci- und Lucasfolge

Table 7: Werte der erweiterten Fibonacci- und Lucasfolge

n	-9	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9
Fn	34	-21	13	-8	5	-3	2	-1	1	0	1	1	2	3	5	8	13	21	34
Ln	-76	47	-29	18	-11	7	-4	3	-1	2	1	3	4	7	11	18	29	47	76

Die nachfolgend bewiesenen Eigenschaften sind jedoch so nützlich, daß sie erwähnt werden.

2.3.1 F_-n

F_-n = (- 1)^{n+1 .} F_n

2.3.1.1 Beweis:

Die Richtigkeit der für den Induktionsanker erforderlichen Fälle n=0 sowie n=1 kann anhand der Tabelle geprüft werden. Gelte nun nach Induktionsannahme die oben genannte Beziehung. Zu zeigen bleibt die Richtigkeit für (n+1):

F_-(n+1) = F_-(n-1) - F_-n = (- 1)^{(n-1)+1 .} F_n-1 - (- 1)^{n+1 .} F_n = (- 1)ⁿF_n-1 + (- 1)ⁿF_n

= (- 1)ⁿ(F_n-1 + F_n) = (- 1)ⁿF_n+1 = (- 1)^(n+1)+1F_n+1

2.3.2 L_-n

L_-n = (- 1)^{n .} L_n

2.3.2.1 Beweis:

Die Richtigkeit der für den Induktionsanker erforderlichen Fälle n=0 sowie n=1 kann anhand der Tabelle geprüft werden. Gelte nun nach Induktionsannahme die oben genannte Beziehung. Zu zeigen bleibt die Richtigkeit für (n+1):

L_-(n+1) = L_-(n-1) - L_-n = (- 1)^{(n-1) .} L_n-1 - (- 1)^{n .} L_n = (- 1)^n-1L_n-1 + (- 1)^n-1L_n

= (- 1)^n-1(L_n-1 + L_n) = (- 1)^n-1L_n+1 = (- 1)ⁿ⁺¹L_n+1