Wir bezeichnen mit n die Zahl, die es zu zerlegen gilt, mit Fn die gesuchte Anzahl der Darstellungen
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.
- Schritt.Man addiert zu den FN Darstellungen der Zahl N jeweils die 1 (. Man hängt an jede dieser Darstellungen die Zahl 1 an) .
- 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