10. Lineare Differenzengleichungen und die Herleitung der Formel von Binet

Historisch gesehen, waren vom Zeitpunkt der ersten Beschreibung der Fibonacci-Zahlen im Liber Abaci (im Jahre 1202) bis zur Formulierung der Formel von Binet (im Jahre 1843) Jahrhunderte vergangen. Heute stellt die Theorie der Differenzengleichungen Methoden zur Verfügung, um für große Klassen rekursiver Gleichungen in systematischer Weise (nichtrekursive) „explizite“ Darstellungen (bzw. Darstellungen „in geschlossener Form“) zu finden. In diesem Kapitel wird exemplarisch eine solche Möglichkeit zur Herleitung der Formel von Binet behandelt. Typologisch betrachtet, ist die Definitionsgleichung der Fibonacci-Zahlen eine lineare Differenzengleichung zweiter Ordnung (mit konstanten Koeffizienten). Aufbauend auf der Tatsache, dass die Lösungen linearer Differenzengleichungen erster Ordnung (mit konstanten Koeffizienten) geometrische Folgen sind, wird der Versuch unternommen, lineare Differenzengleichungen zweiter Ordnung additiv in jeweils zwei lineare Differenzengleichungen erster Ordnung zu zerlegen. Dies führt zur „charakteristischen Gleichung“ der ursprünglich gegebenen Differenzengleichung, mit deren Wurzeln schließlich in kanonischer Weise die Lösungen der Fibonacci-Gleichung konstruiert werden.