Lücken füllen

Wer kennt sie nicht, Knobelaufgaben der Art: Gegeben sind die Zahlen 3, 8, 20, 39 und 65 – welche Zahlen folgen? So beginnt unter der Überschrift Quo vadis, sequentia? ein Artikel aus dem Jahr 2010. Darin notierte ich, dass es auf solche Fragen immer mehrere Antworten gibt. Ich stellte auch eine Methode vor, um jede Folge begründet weiterzuführen: Man findet das Polynom kleinsten Grades, welches die Folgenglieder eines nach dem anderen ausspuckt und danach beliebig viele weitere.

Im vorigen Monat stellte mir Dominic eine ähnliche Knobelei vor:

83, 18, 20, x, 10, 12, 4, 21, y, 24, 13, 84

Kannst du die richtigen Zahlen für x und y einsetzen?

Mir war zwar bewusst, dass Dominic bei diesen Zahlen kein Polynom als Bildungsregel im Sinn hatte. Trotzdem war mein Interesse geweckt, die Methode aus Quo vadis, sequentia? so zu erweitern, dass sie nicht nur Folgen am Ende fortführen kann, sondern auch Lücken in einer Folge schließen. Ich möchte hier am Beispiel der Zahlenfolge

zeigen, wie es gelingt. Da sich die Methode automatisieren lässt, setzte ich sie außerdem in einem Programm um, welches Lücken in Zahlenfolgen selbsttätig schließt.

Mit a und b können wir die Lücken in der Folge zunächst benennen: 0, 6, a, 0, 0, b, 36. Nun kann man im Prinzip wie in Quo vadis, sequentia? ein Differenzendreieck erstellen:

Die erste Zeile enthält unsere Zahlenfolge. Jeder andere Eintrag ist die Differenz aus dem Eintrag rechts darüber und jenem direkt darüber, beispielsweise:

So produziert man oben angefangen Zeile um Zeile, bis eine Zeile unten nur noch so viele Einträge enthält, wie Lücken in der Zahlenfolge aufzufüllen sind. Im Beispiel sind das zwei Einträge in der letzten Zeile, da mit a und b zwei Lücken zu füllen sind.

Die Einträge der letzten Zeile werden nun null gleichgesetzt, wodurch wir ein lineares Gleichungssystem erhalten:

Um das Gleichungssystem zu lösen, kann man beispielsweise das Gauß’sche Eliminationsverfahren anwenden. Das Ergebnis stopft die Lücken in unserer Zahlenfolge: a = 4 und b = 10. In der Hauptsache ist die Aufgabe damit erfüllt. Zusätzlich ist oft wünschenswert, als Begründung für die Wahl dieser Zahlen eine Bildungsregel anzugeben, aus der sich die Glieder der Folge inklusive Lückenfüllungen ergeben.

Um die Bildungsregel zu komponieren, benötigen wir aus dem Differenzendreieck allein die erste Spalte. Lass dich nicht davon irritieren, dass ich grau hinterlegt Bezeichnungen ergänze:

Da wir a = 4 und b = 10 schon kennen, können wir die Buchstaben ersetzen, und aus der Spalte wird dies:

In Quo vadis, sequentia? leitete ich eine allgemeine Formel für das Interpolationspolynom her:

Die Formel mag einschüchternd wirken, aber es steckt keine hohe Mathematik darin. Ich werde sie gleich mit Leben füllen. Doch zunächst stelle ich ihre Bestandteile vor.

Das Σ ist eigentlich der Großbuchstabe Sigma aus dem griechischen Alphabet und steht hier für eine Summe, also fürs wiederholte Plus-Rechnen. Π steht für ein Produkt, also fürs wiederholte Malnehmen. Es ist dem griechischen Großbuchstaben Pi nachempfunden. k und j sind Zähler, die man nacheinander mit den Zahlen von 0 bis, was auch immer über dem Σ oder Π steht, belegt. d_0,k ist ein Eintrag aus der ersten Spalte des Differenzendreiecks. Das große K ist in unserem Fall 3, weil sich in der ersten Spalte unseres Differenzendreiecks d_0,k das letzte mal bei k = 3 von null unterscheidet. Zu guter Letzt ist x eine unabhängige Variable. Später wird man beliebige Werte anstelle von x einsetzen können, aber dafür müssen wir x zunächst als Platzhalter erhalten.

Auf unser Beispiel angewandt stellt sich die Formel so dar:

Nach fröhlichem Addieren, Kürzen und Tilgen überflüssiger Nullen bleibt davon:

Wenn man die Klammern ausmultipliziert und zusammenzählt, was geht, erhält man eine bescheidene Funktion als Bildungsregel:

Setzt man für x in der gefundenen Bildungsregel zur Probe die Zahlen 0, 1, 2, 3, … ein, antwortet sie mit den Gliedern der gegebenen Folge einschließlich der Lösungen für die Lücken. So soll es sein!