Optimales Polynom

Problem 101

Wenn man die ersten k Terme einer Folge gezeigt bekommt, ist es unmöglich, mit Gewissheit den Wert des nächsten Terms zu sagen, denn es gibt unendlich viele Polynomfunktionen, die die Folge abbilden können.

Als Beispiel betrachten wir die Folge der Kubikzahlen. Diese ist definiert durch die Bildungsfunktion
un = n3: 1, 8, 27, 64, 125, 216, ...

Angenommen, uns werden nur die ersten zwei Terme dieser Folge gegeben. Wenn wir mit dem Prinzip "einfacher ist besser" arbeiten, sollten wir eine lineare Beziehung annehmen und für den nächsten Term 15 vorhersagen (gemeinsame Differenz 7). Selbst wenn uns die ersten drei Terme gezeigt werden, sollte nach dem Prinzip der Einfachheit eine quadratische Beziehung angenommen werden.

Wir definieren OP(k, n) als den n-ten Term der optimalen Polynomfunktion für die ersten k Terme der Folge. Es sollte ersichtlich sein, dass OP(k, n) die Terme für nk korrekt generieren wird, und potenziell der erste inkorrekte Term (FIT) OP(k, k+1) sein wird; in diesem Fall nennen wir ihn einen schlechten OP (BOP).

Als Basis, wenn uns nur der erste Term gegeben würde, wäre es am sinnvollsten, Konstanz anzunehmen; das bedeutet, für n ≥ 2, OP(1, n) = u1.

Somit erhalten wir die folgenden OPs für die kubische Folge:

OP(1, n) = 1 1, 1, 1, 1, ...
OP(2, n) = 7n−6 1, 8, 15, ...
OP(3, n) = 6n2−11n+6 1, 8, 27, 58, ...
OP(4, n) = n3 1, 8, 27, 64, 125, ...

Offensichtlich existieren keine OPs für k ≥ 4.

Betrachtet man die Summe der FITs, die durch die BOPs gebildet werden (oben in rot markiert), erhalten wir 1 + 15 + 58 = 74.

Betrachten Sie die folgende Polynomfunktion zehnten Grades:

un = 1 − n + n2n3 + n4n5 + n6n7 + n8n9 + n10

Finden Sie die Summe der FITs für die BOPs.