Now that we are on the other side of Problem 100, it starts to become exciting. Problem 101 is the first problem we should tackle in Project Euler. A problem which is about polynomials and therefore have links to the currently ongoing problems in UVa Online jugde. The problem reads

If we are presented with the firstkterms 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, …

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 OP(k,n) to be then^{th}term of the optimum polynomial generating function for the firstkterms of a sequence. It should be clear that OP(k,n) will accurately generate the terms of the sequence forn≤k, and potentially thefirst incorrect term(FIT) will be OP(k,k+1); in which case we shall call it abad 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, forn≥ 2, OP(1,n) =u_{1}.

Hence we obtain the following OPs for the cubic sequence:

OP(1,n) = 11, 1, 1, 1, …OP(2,n) = 7n-61, 8, 15, …OP(3,n) = 6n^{2}-11n+61, 8, 27, 58, …OP(4,n) =n^{3}1, 8, 27, 64, 125, …

Clearly no BOPs exist fork≥ 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.