Wieder einmal eine Fibonacci-Folge

Eine Aufgabe aus der Landesrunde einer Mathematikolympiade der neunziger Jahre (Klassenstufe 5).


Jede natürliche Zahl lässt sich als Summe darstellen, in der nur die Summanden 1 oder 2 vorkommen. So gibt es für die Zahl 3 die folgenden Darstellungen:

Stelle auf diese Weise die Zahlen 4, 5 und 6 dar. Wie viele Möglichkeiten gibt es jeweils?
Versuche, eine Regel herauszufinden, nach der sich die Zahl der Möglichkeiten ergibt. Setze nun voraus, dass die gefundene Regel für alle natürlichen Zahlen gilt. Bestimme nach dieser Regel sodann die Anzahl der Möglichkeiten, die Zahl 10 als Summe mit den Summanden 1 und 2 darzustellen.

Wir bezeichnen mit n die Zahl, die es zu zerlegen gilt, mit Fn die gesuchte Anzahl der Darstellungen

fibo

Bis hierher geht es gut nach der Regel Fn+2 = Fn+1 + Fn

In Worten: Jedes Glied der Folge ergibt sich als Summe der beiden vorhergehenden Glieder. Solche Folgen nennt man Fibonacci-Folgen. Die hier vorliegende hat die Anfangsglieder 1, 2.

Die ersten zehn Glieder der Folge sind 1, 2, 3, 5, 8, 13, 21,34, 55, 89.
Es gibt demnach 89 Möglichkeiten, die Zahl 10 als Summe darzustellen, in der nur die 1 und 2 als Summanden vorkommen.

Freilich ist durch das Erraten der genannten Gesetzmäßigkeit noch nicht erwiesen, dass sie für Zahlen größer als 6 gilt.
Aber das Schema, nach dem die Darstellungen bis n = 6 explizit ausgeführt worden sind, enthält schon einen Tipp für einen Beweis, dass hier tatsächlich die beschriebene Fibonacci-Folge für alle natürlichen Zahlen gilt.

Die Regel gelte für eine natürliche Zahl N>3 ( Induktionsvoraussetzung; sie ist bestätigt durch die explizite Ausrechnung).

Wir kommen nun zum Induktionsschluss.

Wie entsteht nun FN+1 ? In zwei Schritten.

  1. Schritt. Man addiert zu den FN Darstellungen der Zahl N jeweils die 1 (. Man hängt an jede dieser Darstellungen die Zahl 1 an) .
  2. Schritt. Man addiert zu den FN-1 Darstellungen der Zahl N-1 die Zahl 2 ( hängt die Zahl 2 an jede dieser Darstellungen an).

Das sind zusammen FN + FN-1 Darstellungen. Sind das schon alle?

Was würde geschehen, wenn man im Schritt 1 die angehängte 1 mit einer 1 im „Innern“ der Darstellung vertauscht? ( Das „Innere“ der Darstellung ist bei der expliziten Rechnung oben normal gedruckt, die angehängte Ziffer fett) .Das wäre offenbar keine neue Darstellung. Wenn man im Schritt 1 die angehängte 1 mit einer 2 im Innern der Darstellung vertauscht? Dann landet man bei einem Fall, der in Schritt 2 berücksichtigt wird.

Ebenso im Schritt 2: Vertauschen der angehängten 2 mit einer 2 im „Innern“ der Darstellung ergibt keine neue Darstellung; Vertauschen der 2mit einer 1 im Innern führt zu einem Fall nach Schritt 1.

Damit gilt FN+1 = FN + FN-1