Rekursion, Fibonacci-Folge
W. Jock

Didaktische Aspekte

Beschreibung

Rekursive Darstellungen sind für Folgen charakteristisch. Mit ihnen lassen sich in einer einfachen Weise Vorgänge beschreiben, die in diskreten Schritten ablaufen, wobei einer auf dem vorhergehenden fußt. Viele numerische Rechenverfahren (z.B. das allgemeine Itera- tionsverfahren, das Newtonsche Verfahren) sind rekursiv aufgebaut. Mit dem folgenden Arbeitsblatt sollen die Schülerinnen und Schüler ein erstes Grundverständnis für Rekursionen erwerben und darüber hinaus mit der Folge der Fibonacci-Zahlen, die auch heute noch Gegenstand mathematischer Forschungen ist, ein berühmtes Beispiel kennen lernen.

Methodische Hinweise

Mit der Bearbeitung der einzelnen Fragen soll die Eigentätigkeit der Schülerinnen und Schüler im Sinne eines experimentellen und entdeckenden Mathematikunterrichts angesprochen werden. An vielen Stellen kann das Beweisverfahren der vollständigen Induktion an interessanten, nichttrivialen Beispielen geübt werden. Je nach Unterrichtssituation lassen sich Erweiterungen vornehmen und zum Beispiel die Verbindungen zur Geometrie (goldenes Rechteck, goldene Spirale, spira mirabilis usw.) weiter aufzeigen. Eine ausführliche Darstellung dieser Sachverhalte findet man in:

Beutelsbacher, Petri: Der goldene Schnitt, BI-Verlag, Mannheim, 1988;

Walser: Der goldene Schnitt, Teubner-Verlag, Stuttgart, 1993.

Das CAS dient in erster Linie als Werkzeug zur Beschaffung von Daten, aus denen die Schü- lerinnen und Schüler Vermutungen ablesen sollen, die dann, soweit es vom Kenntnisstand her möglich ist, bewiesen werden. Eine ausführliche und sorgfältige Dokumentation ist daher unerlässlich.

Bei den Aufgaben eins bis fünf ist ein CAS nützlich, aber nicht unbedingt erforderlich. Man kann die zu beweisenden Formeln auch vorgeben. Für die Schülerinnnen und Schüler ist es aber sicher gewinnbringender, wenn sie aus dem vorliegenden Datenmaterial selbst Zusammenhänge entdecken, wobei stellenweise (z.B. bei Aufgabe 5) Hinweise vom Lehrer erforderlich sein werden.

Vorkenntnisse
Folgen, Grenzwert von Folgen, Vollständige Induktion


Aufgabenblatt
Eine reelle Zahlenfolge wird oft durch ein Bildungsgesetz definiert. Dabei unterscheidet man zwei Fälle:

a.) Das Bildungsgesetz ist eine explizite Vorschrift, die die unmittelbare Berechnung jedes Folgenglieds gestattet, z.B.

  .

 

b.) Das Bildungsgesetz ist eine rekursive Vorschrift, durch die ein Folgenglied erst dann be-rechnet werden kann, wenn sein Vorgänger oder mehrere Vorgänger bekannt sind, z.B.

 

 .

Bei einer solchen Vorschrift müssen das erste Folgenglied, z.B. f(1) = 1, g(1) = 3, oder die ersten Folgenglieder, z:B. h(1) = 1, h(2) = 2, bekannt sein.

Aufgabe 1:

Gegeben ist die Folge f mit

 
Bestimmen Sie eine explizite Darstellung der Folge.

Aufgabe 2:

Leonardo von Pisa (geb. 1175), genannt Fibonacci, d.h. Sohn des Bonacci, veröffentlichte 1202 sein Buch liber abbaci, mit dem er die Vorzüge des arabischen Zahlsystems gegenüber dem römischen aufzeigen wollte. Das Buch enthält u.a. die berühmte Fibonnaci-Folge, auf die er bei der Frage nach der Vermehrung von Kaninchen stieß. Ab dem 19. Jahrhundert wurde die Folge zu einem Studienobjekt der Mathematiker. Der Grund für das große Interesse liegt einmal in der Vielfalt der Beziehungen zwischen den Folgengliedern, zum andern aber auch in dem Auftreten der Folge in verschiedenen innermathematischen und außermathematischen Gebieten.

Die Folge f mit  für 

und den Anfangswerten 

heißt Fibonacci - Folge.
Berechnen Sie die ersten 10 Glieder der Folge im Kopf.
Benutzen Sie zur Bestimmung von f(n) für große n die folgende Maple-Prozedur:

f:= proc(n: nonnegint)
option remember;
if n = 1 then 1
elsif n = 2 then 1
else f(n - 2) + f(n -1) fi
end;

Bestimmen Sie f(10), f(50), f(100), f(150). Löschen Sie dann in der Prozedur die Anweisung option remember; und führen Sie die Berechnung von f(50) erneut durch. Was bewirkt also die Anweisung?

Fügen Sie die Anweisung wieder in den Prozedurtext ein.

Aufgabe 3:

Die ersten k Fibonacci-Zahlen fassen wir zu einer Liste zusammen, um auf die einzelnen Glieder der Folge zugreifen zu können. Testen Sie die folgende Anweisung, indem Sie für k verschiedene Werte einsetzen:

Liste:= [seq (f(i), i = 1.. k)];

Welche Werte werden durch Liste[3], Liste[8] usw. ausgegeben?

Aufgabe 4:

Mit der Anweisung

f(8), sum (´f(n)´, n = 1..8), sum(´f(n)^2´, n = 1..8);

werden die Fibonacci-Zahl f(8), die Summe der ersten 8 Fibonacci-Zahlen und die Summe der Quadrate der ersten 8 Fibonacci-Zahlen nebeneinander ausgegeben.

Wir verwenden diese Anweisung in einer for-Schleife:

for k from 1 to 15 do
f(k), sum(´f(j)´ j = 1.. k), sum(´f(j)^2´, j = 1.. k)
od;

 

  1. Versuchen Sie mit Hilfe des erhaltenen Zahlenmaterials, die Summe der Quadrate der ersten k Fibonacci-Zahlen (k = 1,2,3,....) durch das Produkt zweier Fibonacci-Zahlen darzustellen. Beweisen Sie Ihre Vermutung.
  2. Suchen Sie ebenso eine Darstellung für die Summe der ersten k Fibonacci-Zahlen.
  3. Beweisen Sie Ihre Vermutung mit vollständiger Induktion.
 
Aufgabe 5:
  1. Berechnen Sie für einige Werte von k () jeweils das Produkt zweier benachbarter Fibonnacci-Zahlen, also   usw.. Versuchen Sie dann, die Produkte jeweils durch zwei andere Fibonacci-Zahlen auszudrücken. Beweisen Sie die vermutete Formel mit vollständiger Induktion.
  2. Berechnen Sie für einige Werte von k (.
  • Versuchen Sie dann, die Quadrate  durch andere Fibonacci-Zahlen auszudrücken. Beweisen Sie die vermutete Formel.
  • Aufgabe 6:

    Stellen Sie für  die Punkte (n/f(n)) in einem Koordinatensystem dar. Das Schaubild legt die Vermutung nahe, daß die Punkte angenähert auf dem Graphen einer Exponentialfunktion g mit  liegen könnten.

    Begründen Sie, dass beim Zutreffen dieser Vermutung die Punkte (n/ln(f(n)) auf einer Geraden liegen müssten. Überprüfen Sie Ihre Vermutung durch eine graphische Darstellung der Punkte.

    Sie können dazu folgendermaßen vorgehen:

    Erzeugung der Punkte:

    Punkte1:= [seq ( [n, f(n)], n = 1..15) ]:

    Mit den Anweisungen

    with(plots):
    pointplot(Punkte1);

    erhalten Sie dann die gewünschte Darstellung.

    Für den zweiten Teil der Aufgabe erzeugen Sie mit der Anweisung:

    Punkte2:= [seq ( [n, log(n) ], n = 1..15]:

    die entsprechenden Punkte, die wie oben im Koordinatensystem dargestellt werden können

    Führen Sie dies durch für verschiedene Wertebereiche von n (z.B. usw.) und überprüfen Sie jedes Mal Ihre Vermutung.

    Maple gibt Ihnen sogar die Gleichung der "Ausgleichsgeraden" an, die man durch die Punkte legen kann. Es seien n Punkte  i = 1...n vorgegeben. Die Ausgleichsgerade durch diese Punkte ist die Gerade g: y = mx + c, für die die Summe der quadratischen Abweichungen

    ein Minimum wird.

    Verdeutlichen Sie sich dies zunächst an einem einfachen Beispiel. Gegeben seien die drei Punkte 
     

    Mit den Anweisungen

    with(stats): with(fit): with(statplots):
    leastsquare [ [x,y], y = m*x + c , {m,c}] ( [ [1,2,4], [2,4,5] ] );

    bestimmt Maple die Gleichung der Ausgleichsgeraden durch die drei Punkte. Um mit der erhaltenen linearen Gleichung als Funktionsgleichung arbeiten zu können, muß noch die Anweisung

    g:= unapply( rhs(´´), x);

    eingegeben werden. Nun können Sie mit dem display - Befehl die Punkte und die Ausgleichs- gerade in ein Koordinatensystem zeichnen.Verändern Sie die Ordinaten der Punkte oder fügen Sie einen vierten Punkt ein. Lassen Sie sich jedes Mal die Gleichung der Ausgleichsgeraden angeben.

    Bei dem ursprünglichen Problem erhalten Sie die Gleichung der Ausgleichsgeraden mit den Befehlen

    Liste1:= [seq(n, n = 1..15)]:
    Liste2:= [seq( ( evalf(log(f(n) ) ), n = 1..15]:
    leastsquare [ [x,y], y = m*x + c , {m,c}] ( [ Liste1, Liste2]);
    f1:= unapply( rhs(), x);

    Bestimmen Sie für die von Ihnen gewählten Bereiche von n jeweils die Gleichung der Ausgleichsgeraden.

    Was fällt ihnen auf?

    Bestimmen Sie dann aus der Gleichung der Ausgleichsgeraden Näherungswerte für f(10), f(100) usw. und vergleichen Sie mit den exakten Werten.

    Aufgabe 7:

    Die Überlegungen zu Aufgabe 7 legen es nahe, für f(n) einen exponentiellen Ansatz zu machen: Ermitteln Sie aus der Gleichung  mit dem Ansatz  Werte für b und a. Wie hängen diese Werte mit den in Aufgabe 6 bestimmten Werten für m und c zusammen?

    Aufgabe 8:

    Der französische Mathematiker Binet veröffentlichte mehr als 600 Jahre nach dem Erscheinen des liber abbaci eine explizite Darstellung für die Fibonacci-Zahlen:

    .

    Beweisen Sie diese Formel mit vollständiger Induktion

    Begründen Sie mit der Formel von Binet die in Aufgabe 8 durchgeführten Näherungen. Was ist das Besondere an dieser Formel?

    Aufgabe 9:

    Untersuchen Sie nun noch die Folge

    Lassen Sie sich von Maple die ersten Folgeglieder ausgeben. Welche Vermutung haben Sie?

    Zeigen Sie, daß gilt:

    .

    Nehmen Sie an, daß die Folge g konvergiert. Berechnen Sie unter dieser Annahme aus der letzten Formel den Grenzwert.

    Bemerkungen:

    1. Die einzelnen Fibonacci-Zahlen erhält man mit Maple auch durch die Anweisungen:
    with(combinat, fibonnaci):
    fibonnaci(8);
    1. Maple berechnet die Formel von Binet aus der rekursiven Darstellung mit der Anweisung:
    rsolve( {f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1}, f(n));
     
    zurück
     aufbereitet fürs Internet: Roland Bernert