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
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):
Ü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?