[zurück]

Zum Goldenen Schnitt und zur Fibonacci-Folge

(Christoph Pöppe) 		[vor]

Ein Experimentalphysiker, ein theoretischer Physiker und ein Mathematiker werden jeder hungrig in eine Zelle gesperrt, mit nichts als einer verschlossenen Blechdose: Hering in Tomatensoße oder so. Am nächsten Morgen sieht man nach, wie jeder sein Problem bewältigt hat. - Die Zelle des Experimentalphysikers ist übel zugerichtet: überall Macken in der Wand vom Aufprall der Dose, von verschiedenen Stellen der Decke tropft die Soße, aber der Gefangene fummelt glücklich mit dem Finger den Fisch aus der Dose. - Der theoretische Physiker speist ebenfalls, aber seine Zelle sieht besser aus. Er hat nämlich zuerst umfangreiche Flugbahnberechnungen angestellt und dann sein Ziel mit einem einzigen wohlgezielten Wurf erreicht. - Der Mathematiker sitzt vor der geschlossenen Dose - und ist ebenfalls glücklich, denn er sagt: Angenommen, diese Dose wäre offen ...

Wie beweist man, dass der Quotient fn+1/fn aufeinanderfolgender Glieder der Fibonacci-Folge gegen t strebt?

Gib der Folge der Quotienten zunächst einen Namen: qn = fn+1/fn. Um zu beweisen, dass qn gegen t strebt (in Formeln: qn ® t für n ® ¥ oder auch limn ® ¥ qn = t), versuche zunächst, etwas Brauchbares über qn rauszukriegen: Bildungsgesetz oder so. Das einzige, was du zur Verfügung hast, ist die Rekursionsformel fn = fn-1+fn-2. Munter drauflos:

qn = fn+1
fn		 = fn+fn-1
fn		 = 1 + fn-1
fn		 = 1 + 1 
qn-1

Das ist ein brauchbares Bildungsgesetz für qn. Jetzt wende das Fischdosenprinzip an: Angenommen, die Folge qn hätte einen Grenzwert. Dann könnte es erstens nur einer sein (das ist immer so bei Grenzwerten); nennen wir ihn q. Zweitens müsste er die Gleichung q = 1+1/q erfüllen. (Gehe auf beiden Seiten der obigen Gleichung zum Grenzwert über.) Das ist eine quadratische Gleichung für q; eine der beiden Lösungen ist t, die andere -1/t, die scheidet sofort aus, weil der Quotient nie negativ ist.

Also: Wenn die Folge qn einen Grenzwert hat, kann es nur t sein. Hat sie einen Grenzwert? Ja. Das kann man zum Beispiel beweisen, indem man nachrechnet, was mit den Differenzen aufeinanderfolgender qn passiert (wieder das Bildungsgesetz einsetzen, aufn Hauptnenner bringen):

qn - qn-1 = 1 
qn-1		 - 1 
qn-2		 = qn-2 - qn-1
qn-1qn-2

Was sieht man? Die Differenz wechselt jedesmal das Vorzeichen, wenn n eins größer wird, und vor allem wird sie mit jedem Schritt immer kleiner, denn was da im Nenner steht, ist spätestens ab n = 2 deutlich größer als (3/2)2. Also geht die Differenz gegen null (und zwar mindestens so schnell wie eine geometrische Folge), und sie wechselt dauernd das Vorzeichen, dann bleibt der Folge qn nichts übrig, als zu konvergieren (Leibniz-Kriterium).

Wenn man ein bestimmtes Glied fn der Fibonacci-Folge ausrechnen will, hat aber keine Lust, die Rekursionsformel anzuwenden, weil das für große n eine tierische Rechnerei wird, kann man die Binetsche Formel anwenden:

fn = 1
Ö5
 (tn - (-t)-n)

Wie kommt man dadrauf? Wieder Fischdosenprinzip. Ignoriere vorläufig die Anfangsbedingungen f1 = 1, f2 = 1 und nimm an, du hättest eine Lösung für die Rekursionsgleichung fn = fn-1+fn-2, aber in besonders einfacher Form: fn = zn mit vorläufig noch unbekanntem z (geometrische Folge). Welchen Wert müsste dann z haben? Einsetzen:

zn = zn-1+zn-2

Die Möglichkeit z = 0 bringt nichts, also dividiere durch zn-2:

z2 = z+1

Die kennen wir doch schon! Das ist die quadratische Gleichung mit den Lösungen t und -1/t. Also: tn und (-t)-n sind Lösungen der Rekursionsgleichung. Na schön. Aber es gibt noch mehr. Die Rekursionsgleichung ist nämlich linear. Wenn man eine Folge, die die Rekursionsgleichung löst, mit einem konstanten Faktor multipliziert oder zwei solcher Folgen (Glied für Glied) addiert, kommt wieder eine Lösung raus: Alles, was die Form atn + b (-t)-n hat, löst die Rekursionsgleichung.

Jetzt kriegen wir die Fischdose endgültig auf. Wähle a und b so, dass die bislang ignorierten Anfangsbedingungen erfüllt sind:

f1 = at + b(-1/t) = 1
f2 = at2 + b(1/t)2 = 1

Zwei Gleichungen mit den zwei Unbekannten a und b, kommt raus (nach lästiger Rechnerei mit t, t2 und so weiter):
a = 1
Ö5		 ,     b = - 1
Ö5

Also:
fn = 1
Ö5		 (tn - (-t)-n),

quod erat demonstrandum.

Ziemlich verrückt eigentlich: Die Formel verknüpft lauter irrationale Größen wie t und Ö5, und heraus kommt für jedes n etwas Ganzzahliges!

Wieso funktioniert der Trick mit dem Ansatz fn = zn eigentlich? Weil die Rekursionsgleichung fn = fn-1+fn-2 linear ist, das heißt, Lösungen der Rekursionsgleichung darf man addieren und mit einem konstanten Faktor multiplizieren. Deswegen kann man nämlich jede Lösung der Rekursionsgleichung, insbesondere die Fibonacci-Folge selbst, aus diesen besonders einfachen Lösungen (den Basislösungen) zusammensetzen. Es müssen halt genauso viele freie Parameter (im Beispiel a und b) zur Verfügung stehen, wie Bedingungen (im Beispiel: f1 = 1, f2 = 1) zu erfüllen sind. Denn ein lineares Gleichungssystem ist im allgemeinen genau dann lösbar, wenn es genauso viele Gleichungen hat wie Unbekannte.

Allgemein gilt: Wenn das Wesentliche, was man in der Hand hat, eine Rekursionsformel ist, dann ist das Schönste, was man damit machen kann, ein Induktionsbeweis. Das hat uns Britta eindrucksvoll vorgemacht.

Die Aufgabe lautet: Beweise, dass fkn ein ganzzahliges Vielfaches von fn ist, oder, was auf dasselbe hinausläuft: Jede n-te Fibonacci-Zahl ist ein Vielfaches von fn. Die Aufgabe steht auf einer von drei sehr ergiebigen (englischen) Websites zum Thema: Fibonacci Numbers and the Golden Section, The Mathematics of the Fibonacci series und Easier Fibonacci puzzles.

Beweis durch Induktion (von Britta): Beweise zunächst eine Hilfsbehauptung:

fn = fi+1 fn-i + fi fn-i-1     für i = 1,2,..., n-2

und zwar ebenfalls durch Induktion.

Das Prinzip ist: Beweise die Behauptung für den Spezialfall i = 1 (Induktionsanfang); beweise dann, dass man unter der Voraussetzung, dass sie für irgendein i gilt, ihre Gültigkeit für i+1 schließen kann (Induktionsschritt). Dann hast du sie für alle i = 1,2,... bewiesen. Du hast nämlich einen Aufhängepunkt für eine Kette bereitgestellt und eine Anweisung, eine bereits vorhandene Kette um ein Glied zu verlängern. Damit kannst du beliebig lange Ketten konstruieren.

Jetzt geht's aber los. Induktionsanfang: Die Hilfsbehauptung für i = 1 lautet fn = f2 fn-1 + f1 fn-2. Aber f1 = f2 = 1, also steht da nichts weiter als die Rekursionsformel, und die ist offensichtlich richtig. Induktionsschritt: Es ist zu beweisen (setze i+1 an die Stelle von i):

fn = f(i+1)+1 fn-(i+1) + fi+1 fn-(i+1)-1

Forme die rechte Seite der Behauptung um:

... = fi+2 fn-i-1 + fi+1 fn-i-2
trickreich denselben Term einmal addieren und wieder subtrahieren:
= fi+1 (fn-i-1 + fn-i-2) + (fi+2 - fi+1)fn-i-1
Rekursionsformel anwenden: fn-i-1 +fn-i-2 = fn-i und fi+2 - fi+1 = fi
= fi+1 fn-i + fi fn-i-1
= fn nach Induktionsvoraussetzung, denn das ist gerade die Hilfsbehauptung für i.

Das war's schon für die Hilfsbehauptung.

Jetzt die Behauptung selbst, zu beweisen durch Induktion über k. Induktionsanfang: Für k = 1 ist zu zeigen: fn ist ein Vielfaches von fn. Das ist offensichtlich richtig. Induktionsschritt: Es ist zu zeigen, dass f(k+1)n ein Vielfaches von fn ist. Forme f(k+1)n um, indem du die Hilfsbehauptung für i = n anwendest:

f(k+1)n = fn+1 f(k+1)n-n + fn f(k+1)n-1

Der zweite Summand ist offensichtlich ein Vielfaches von fn (steht ja da). Der erste Summand ist ein Vielfaches von fn, denn nach Induktionsvoraussetzung ist f(k+1)n-n = fkn ein Vielfaches von fn. Also ist die Summe ein Vielfaches von fn. Fertig!

[zurück] [Inhaltsverzeichnis] [vor]