Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Fibonaccizahlen

Ich habe 8 Urgrosseltern und 2n+2 Urngrosseltern. Bei der Honigbiene sieht das aber ganz anders aus. Die Königin kann unbefruchtete Eier ablegen---das werden dann die Drohnen (die männlichen Tiere)---oder aber befruchtete Eier, woraus dann eine weibliche Arbeiterin (oder, bei viel Glück auch eine Königin) entsteht. Drohnen haben also eine Mutter aber keinen Vater, sie haben Grossmutter und Grossvater mütterlicherseits, und, da die Grossmutter zwei Elternteile und der Grossvater wieder nur eine Mutter hat, hat die Drohne 3 Urgrosseltern. Die Arbeiterin hat dagegen 5 Urgrosseltern. Rechts ist der Stammbaum der Biene Maja zu sehen:

Sind Wn bzw. Mn die Zahlen der Vorfahren einer Arbeiterin bzw. einer Drohne vor n Generationen, so gilt offensichtlich Mn = Wn-1 und Wn = Wn-1 + Mn-1, also

Wn = Wn-1 + Wn-2 für n > 1.

Diese Rekursionsgleichung ist uns schon früher begegnet. Auch die Anfangsbedingungen W0 = 1 und W1 = 2 sind nach Reindizierung mit den dortigen identisch.

Die Fibonaccizahlen sind die eindeutigen Lösungen der Rekursionsgleichung Fn = Fn-1 + Fn-2 mit den Anfangswerten F0 = F1 = 1. Zuerst erwähnt wurden sie von Fibonacci.

Übungsaufgabe: Gegeben ist die Matrix A = . Berechnen Sie die Matrizen A2, A3, ... solange bis Sie eine Vermutung bekommen, wie die Koeffizienten von An für allgemeines n Î N aussehen. Beweisen Sie Ihre Vermutung durch vollständige Induktion.

Übungsaufgabe: Beweisen Sie Cassini's Ungleichung Fn+1Fn-1 - Fn2 = (-1)n. (Sie dürfen natürlich, wenn Sie wollen, die vorige Aufgabe benutzen. Erinnern Sie sich an den Produktsatz für Determinanten aus der Linearen Algebra?)

Die Ungleichung besagt Fn+1/Fn » Fn/Fn-1, oder auch (Fn+Fn-1)/Fn » Fn/Fn -1 und da die Fibonacci-Zahlen gegen unendlich streben wird der Fehler den wir machen relativ immer kleiner.
Es taucht der goldene Schnitt (etwa 1.618033989) auf. Die Strecke a wird im goldenen Schnitt geteilt a = b+c falls a/b = b/c ist, d.h. falls das Ganze zum größeren Teil sich so verhält wie der größere Teil zum kleineren Teil. Also ist asymptotisch der Quotient zweier aufeinanderfolgender Fibonaccizahlen gleich dem goldenen Schnitt.

Hier können Sie für verallgemeinerte Fibonaccizahlen (mit derselben Rekursion aber beliebigen Anfangswerten) den Quotienten aufeinanderfolgender Folgenglieder berechnen (klappt nur mit natürlichen Zahlen bis 1000000):

an an+1 Quotient:

Übungsaufgabe: Wieviel Strahlen durch eine Doppelglasscheibe gibt es, die genau n mal reflektiert werden? Das Beispiel zeigt die 5 Strahlen für n = 3.

Übungsaufgabe: Zeigen Sie Fn+2 = Fn + Fn-1 + ... + F1 + 2.

Zum Abschluß noch einige Fibonacci-Zahlen in Graphen:

Übungsaufgabe: a) Wieviel unabhängige Mengen gibt es in einem Weg-Graphen Pn?
b) Wieviele maximale unabhängige Mengen hat der rechts abgebildete "Kamm-Graph" bei beliebeiger Länge n?
c) Wieviel unabhängige Mengen hat der Kreis-Graph Cn?


Im WWW sind viele weitere Informationen über Fibonacci und Fibonacci- Zahlen zu finden.
Zurück zu Anzahlen, oder vorwärts zu Rekursionsgleichungen
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.