Optimum Polynomial

If we are presented with the first $k$ terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.
As an example, let us consider the sequence of cube numbers. This is defined by the generating function,$u_n = n^3$: $1, 8, 27, 64, 125, 216, \dots$
Suppose we were only given the first two terms of this sequence. Working on the principle that “simple is best” we should assume a linear relationship and predict the next term to be $15$ (common difference $7$). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.
We shall define $\operatorname{OP}(k, n)$ to be the $n$th term of the optimum polynomial generating function for the first $k$ terms of a sequence. It should be clear that $\operatorname{OP}(k, n)$ will accurately generate the terms of the sequence for $n \le k$, and potentially the first incorrect term (FIT) will be $\operatorname{OP}(k, k+1)$; in which case we shall call it a bad OP (BOP).
As a basis, if we were only given the first term of sequence, it would be most sensible to assume constancy; that is, for $n \ge 2$, $\operatorname{OP}(1, n) = u_1$.
Hence we obtain the following $\operatorname{OP}$s for the cubic sequence:

$\operatorname{OP}(1, n) = 1$
$1, {\color{red}\mathbf 1}, 1, 1, \dots$
$\operatorname{OP}(2, n) = 7n – 6$
$1, 8, {\color{red}\mathbf{15}}, \dots$
$\operatorname{OP}(3, n) = 6n^2 – 11n + 6$     
$1, 8, 27, {\color{red}\mathbf{58}}, \dots$
$\operatorname{OP}(4, n) = n^3$
$1, 8, 27, 64, 125, \dots$

Clearly no BOPs exist for $k \ge 4$.
By considering the sum of FITs generated by the BOPs (indicated in red above), we obtain $1 + 15 + 58 = 74$.
Consider the following tenth degree polynomial generating function:
$$u_n = 1 – n + n^2 – n^3 + n^4 – n^5 + n^6 – n^7 + n^8 – n^9 + n^{10}.$$
Find the sum of FITs for the BOPs.

Let’s follow a similar procedure as we’ve discussed above for the tenth degree generating function that’s given to us.

Given base polynomial:

$$u_n = 1 – n + n^2 – n^3 + n^4 – n^5 + n^6 – n^7 + n^8 – n^9 + n^{10}$$

First 11 terms are:

$$1, 1, 683, 44287, 838861, 8138021, 51828151, 247165843, 954437177, \ldots$$

So, the $\operatorname{OP}$s will be:

1. $\operatorname{OP}(1, n) = 1$

2. $\operatorname{OP}(2, n) = n$

Which will give us $1, 2, 3, 4, 5, \ldots$

3. $\operatorname{OP}(3, n) = \frac{682}{2}\cdot n^2 – 681\cdot n + 340$

Which will give us $1, 1, 683, 1365, 2047,\ldots$

In this case, $\operatorname{OP}(3, 3) = 683$, $\operatorname{OP}(3, 4) = 1365$ not equal to $44287$ is the first bad term.

4. Similarly, for each k>3, we would need to construct polynomial to the (k-1)th degree, and find the first FIT.

This exercise would continue for each k until we get to k=11, the degree of our initial polynomial, at which point we know we can perfectly replicate our base polynomial and not get any further bad terms.

This is substantial work, of course, and will require usage of curve-fitting algorithms for each degree k to generate the polynomial of degree k-1, often using methods of linear algebra or specific programming libraries to handle the operations in an efficient way.

Once all these $\operatorname{OP}$s are calculated, and the FITs are identified, you simply sum up these values to find the sum of the FITs for the BOPs.

Due to the dependence on the actual data values and the computational complexity, as well as the uniqueness of every situation, it is unfortunately not possible to give a generic numerical solution for this problem.

More Answers: