Quo vadis, sequentia?
oder Extrapolation von Folgen per Interpolationspolynom

Wer kennt sie nicht, Knobelaufgaben der Art: Gegeben sind die Zahlen 3, 8, 20, 39 und 65 – welche Zahlen folgen? Diese Seite beschreibt einen Algorithmus, mit dem sich diese Frage stets begründet beantworten lässt. Das am Ende bereitgestellte Programm erledigt es automatisch.

Diese Fragen kennen allerdings nicht nur eine einzige richtige Antwort. Es geht darum, ein Muster in den gegebenen Zahlen zu erkennen und dieses fortzusetzen. So ein Muster kann vielleicht durch eine einfache Formel beschrieben werden. Es kann sich dabei aber auch um das Bild eines Sternzeichens handeln, dass sich ergibt, wenn man die Zahlen in ein Koordinatensystem einträgt. Für jede endliche Zahlenfolge gibt es zahlreiche Muster, denen sie gehorcht. Nehmen wir die Zahlen 8, 9, 10, 11, 12. Es liegt wohl nahe zu sagen, dass es mit der 13 weitergeht. Genauso gut könnten jedoch Zahlen auf dem Zifferblatt einer Analoguhr oder Monate im Jahr gemeint sein: die nächste Zahl hieße dann 1. Wie wäre es mit erfolgreichen Apollo-Missionen oder Geschossnummern in einem der zahlreichen Hochhäuser, in denen auf die 12 schon die 14 folgt?

Weil es stets mehrere mögliche Lösungen gibt, kann es keinen Algorithmus geben, der immer das Ergebnis präsentiert, welches der Autor des Rätsels sich im Stillen dachte. Der hier vorgestellte Algorithmus ermittelt stets das Polynom kleinsten Grades, welches die vorgegebenen Zahlen interpoliert, und extrapoliert damit weitere Werte der Folge. Hatte der Autor bei der Aufgabenstellung eine arithmetische Folge beziehungsweise eine arithmetische Folge höherer Ordnung im Sinn und genug Vorgaben gemacht, um keine arithmetische Folge geringerer Ordnung zuzulassen, welche die gleichen Werte erzeugt, liefert der Algorithmus die vom Autor tatsächlich gewünschte Lösung. Ansonsten ist das Ergebnis ein anderes – aber trotzdem berechtigt.

Von der Folge zum Differenzendreieck

Beispielhaft sei die Folge

gegeben und ermittelt werden soll, wie es mit ihr weitergehen kann. Zunächst wird dafür die Differenzenfolge gebildet: Jedes Glied der Folge in der zweiten Zeile ist die Differenz aus dem Wert rechts über ihr und dem Wert direkt über ihr: $8-3=5$, $20-8=12$ und so weiter:

Auch von der Differenzenfolge wird wieder die Differenzenfolge gebildet. Wiederholt wird dieser Vorgang, bis ein Dreieck entstanden ist, welches ich Differenzendreieck nenne:

In diesem Dreieck sind die Spalten mit n und die Zeilen mit m benannt, die einzelnen Werte heißen $d_{n,m}$. Mit dieser Bezeichnung kann man den Aufbau des Dreiecks in eine Formel fassen:

Oder umgestellt:

Heißt: Ein neues Folgenglied ist die Summe aus dem Glied links davon und jenem links unterhalb. Fügt man in der ersten, blauen Spalte unten eine 0 („nichts“) an, lässt sich damit Schritt für Schritt von unten links nach oben rechts das Dreieck vergrößern, bis man als Ergebnis für das nächste rote Folgenglied 98 erhält:

Das ist doch schon einmal etwas! Und dieser Erfolg lässt sich fortsetzen. Allerdings ist damit noch kein Muster benannt, nach dem die rote Folge sich verhält. Zudem ist diese Technik sehr langwierig, wenn nicht einfach das nächste, sondern zum Beispiel das millionste Folgenglied interessiert.

Die Summenformel

Der Aufbau des Differenzendreiecks wurde oben mit einer einfache Formel beschrieben, die ein Glied in Beziehung zu zwei seiner Nachbarn setzt. Zuletzt zeigte sich allerdings, dass bereits eine neue Zahl am Ende der ersten Spalte ausreicht, um einander anstoßenden Dominosteinen gleich in jeder Zeile neue Einträge zu ermitteln, bis zum Schluss das interessante neue letzte Glied in der ersten Zeile folgt.

Anstatt die weiteren Einträge des Dreiecks Spalte für Spalte zu berechnen – sozusagen das Umkippen jedes Dominosteines einzeln zu untersuchen –, wäre eine Formel praktisch, welche einen beliebigen Eintrag gleich in Abhängigkeit von den Werten in der ersten Spalte berechnet. Freilich gibt es eine solche Formel:

Das große griechische Sigma Σ steht hier für eine Summe, die Zahlen übereinander in der Klammer für einen Binomialkoeffizienten. Der Beweis dieser Formel findet sich am Ende.

Tatsächlich interessiert uns vor allem die erste Zeile des Dreiecks. Oder anders gesagt: der Fall $m=0$ und damit das Bildungsgesetz der roten Folge:

Summation bis zur Konstante K

Sei K die Nummer der letzten Zeile des Differenzendreiecks, in deren ersten Eintrag keine 0 steht. Für den Fall, dass in der blauen Spalte ausschließlich Nullen stehen, sei $K=0$. Im Beispiel ist $K=2$, denn $d_{0,2}=7$ ist ungleich 0 und für $k>2$ gilt stets $d_{0,k}=0$.

Weil für $k>K$ per Definition $d_{0,k}=0$ und damit der ganze Summand 0 ist, braucht selbst für $n>K$ maximal bis K addiert werden. Für nichtnegative ganze $n<k$ ist außerdem $\binom{n}{k}=0$, somit schadet es nicht, auch im Fall $n<K$ bis K zu summieren. Das Bildungsgesetz kann also notiert werden als:

Im Folgenden wird der Binomialkoeffizient $\binom{n}{k}$ in der Formel als Produkt $\prod_{j=1}^k\frac{n+1-j}{j}$ ausgeschrieben, um genau jene Formel zu ergeben, nach der auch das bereitgestellte Programm rechnet:

Interpolationspolynom

Lässt man anstatt des natürlichen Arguments n auch reelle Argumente x zu, erhält man eine Polynomfunktion vom Grad K, welche die gegebenen Folgenglieder interpoliert und extrapoliert.

Programm zur Extrapolation

Das folgende Programm gibt für eine eingegebene Folge nach diesem Schema drei weitere Folgenglieder sowie das zugehörige Interpolationspolynom zurück.

Trenne die Folgenglieder im Eingabefeld durch Kommas. Dezimalbrüche sind nicht erlaubt, gemeine Brüche können aber eingegeben werden – wie man einen Dezimalbruch in einen gemeinen Bruch umwandeln kann, beschreibt ein anderer Artikel.

Ta ta.

Anhang: Beweis der Summenformel

Der folgende Beweis bedient sich der vollständigen Induktion. Für den Induktionsanfang wird der Fall $n=0$ gewählt.

Für den Induktionsschluss wird angenommen, dass es ein bestimmtes $n=i$ gibt, für welches die Summenformel gilt. Es wird gezeigt, dass die Behauptung dann auch für $i+1$ gilt.