wie kann man die Fibonacci-Folge mit Worten herleiten?
x_(n+2) = x_n+x_(n+1)
Anschaulich ist es völlig logisch - ich habe im Heuser davon gelesen unter der Herleitung von Kaninchenpaaren. Wobei ein Kaninchen ein neues Paar erzeugt und im zweiten Monat der Geburt erstmals gebärt.
Dann erhält man ungefähr so etwas:
Nach
1 Monat : 1 Paar (das geboren wurde)
2 Monaten: 1 Paar (nun zeugungsfähig)
3 Monaten: 2 Paare (eines neu)
4 Monaten: 3 Paare (ein Paar neu, eins zeugungsfähig)
5 Monaten: 5 Paare (zwei Paare neu, eines zeugungsfähig)
6 Monaten: 8 Paare …
…
In jedem Monat (Juni z. B.) ist die Anzahl der Kaninchenpaare gleich der Summe der Paaranzahl im Vormonat (Mai) und der Paaranzahl im Vorvormonat (April).
und das kannst Du formelmäßig so…
x n + 2 = x n + x n + 1
…ausdrücken, aber genausogut so:
x n + 1 = x n – 1 + x n
…oder so:
x n = x n – 2 + x n – 1
Diese drei Notationen sind logisch äquivalent.
Also die x_(n+=>2einem Monat zeugungsfähig.
Wenn ich mir meine Tabelle angucke, ist es klar. Ich erkenne
auch einen Algorithmus, der sich wiederholt, aber
grundsätzlich ist dieser ja auch zu beweisen (und damit spiele
ich jetzt nicht auf die vollständige Induktion an, sondern
eher auf ein paar Sätze, wie man die x_n+x_(n+1) herleiten
kann).
Vielleicht bringt der Wikipedia-Artikel ja noch ein wenig Erhellung: