Subsections

2 Grundlegendes

2.1 Formale Definitionen

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

Für die Spezialfälle f0 : = 0, f1 : = 1 definieren die Folgenglieder fn die spezielle bzw. eigentliche Fibonaccifolge, die wir mit (Fn)n $\scriptstyle \in$ $\scriptstyle \mathbb {N}$ oder kurz Fn, manchmal sogar in Funktionsschreibweise mit F bezeichnen wollen. Analog sei die Lucasfolge Ln für L0 : = 2 und L1 : = 1 definiert.

2.2 Einige Eigenschaften

In diesem Abschnitt folgen einige einfach zu beweisende Eigenschaften.


2.2.1 Gemeinsame Teiler

Haben zwei aufeinanderfolgende Glieder fn sowie fn+1 einen gemeinsamen Teiler, so gilt dies für alle Folgenglieder und insbesondere für f0 und f1. 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 fn mod m: Da die Folgenwerte jeweils nur von der Summe ihrer beiden Vorgängerwerte abhängen und da fn mod m lediglich m verschiedene Werte annehmen kann, müssen sich diese Werte periodisch wiederholen. Eine Periode ist gefunden, wenn wir zwei Wertepaare (fr, fr+1) und (fs, fs+1) mit r $ \neq$ s gefunden haben, deren Reste modulo m gleich sind.

Da es höchstens m2 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, m2 + 1$ \left.\vphantom{0,m^{2}+1}\right]$, da dieses Intervall m2 + 1 viele Wertepaare enthält.

2.2.2.2 Beispiel

Betrachten wir die Fn sowie Ln 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 Fn für (F12, F13) $ \equiv$ (F0, F1)  ( mod 8) und bei Ln für (L12, L13) $ \equiv$ (L0, L1)  ( 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. F12n+$\scriptstyle \Delta$ $ \equiv$ F$\scriptstyle \Delta$  ( mod 8)
  2. L12n+$\scriptstyle \Delta$ $ \equiv$ L$\scriptstyle \Delta$  ( mod 8)
  3. Fn $ \equiv$ 0  ( mod 4) $ \Rightarrow$ Fn $ \equiv$ 0  ( mod 8) und n $ \equiv$ 0  ( mod 6)
  4. Ln $ \neq$ 0  ( mod 8)

2.2.2.4 Die letzte Dezimalstelle

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

  1. Fn $ \equiv$ Fn mod 60( mod 10)
  2. Ln $ \equiv$ Ln 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 FL1000 (=3) oder L999 (=6)?

2.3 Negative Indices

Die allgemeine Fibonaccifolge läßt sich auf die ganzen Zahlen ausdehnen, indem wir überall die Gültigkeit der Gleichung fn = fn-1 + fn-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 f0 und f1 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 . Fn

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 . Fn-1 - (- 1)n+1 . Fn = (- 1)nFn-1 + (- 1)nFn

= (- 1)n(Fn-1 + Fn) = (- 1)nFn+1 = (- 1)(n+1)+1Fn+1


2.3.2 L-n

L-n = (- 1)n . Ln

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) . Ln-1 - (- 1)n . Ln = (- 1)n-1Ln-1 + (- 1)n-1Ln

= (- 1)n-1(Ln-1 + Ln) = (- 1)n-1Ln+1 = (- 1)n+1Ln+1

Thorsten Reinecke 2004-07-11