101 : 最適多項式(*)

数列の$k$個の項を与えられたときに, 次の項を確実に求めることは不可能である. その数列に合うような多項式が無限個存在するからである.

例として, 立方数の数列を考えよう. これは生成関数$u_n = n^3$で定義され, 1, 8, 27, 64, 125, 216, ...となる.

この数列の最初の2項のみが与えられているとしよう. "Simple is best"の法則にのっとり, 線形の関係があると仮定し, 3つ目の項が15であると予想する (差分が7). もし最初の3項のみが与えられていたとしても, 同じ原則により, 二次の関係があると仮定して次の項を予測する.

数列の最初の$k$項を生成できる最適な多項式の第$n$項を$\textrm{OP}(k, n)$で表すことにする. 明らかに,$n ≤ k$について$\textrm{OP}(k, n)$は正しい. 最初の異なる項 (First Incorrect Term, FIT) は$\textrm{OP}(k, k+1)$であろう. これを bad OP (BOP) と呼ぶことにする.

原則より, 最初の項しか与えられていない場合には, 定数項とするのが理に適っているだろう; 即ち,$n ≥ 2, \textrm{OP}(1, n) = u_1$.

従って, 立方数の数列について以下のOPを得る.

$\textrm{OP}(1, n) = 1$	1, 1, 1, 1, ...
$\textrm{OP}(2, n) = 7n−6$	1, 8, 15, ...
$\textrm{OP}(3, n) = 6n^2−11n+6$	1, 8, 27, 58, ...
$\textrm{OP}(4, n) = n^3$	1, 8, 27, 64, 125, ...

(BOPを赤くする)

明らかに,$k ≥ 4$のときにはBOPは存在しない.

BOPのFIT (上の例では赤で示されている) の和は,$1 + 15 + 58 = 74$である.

以下の10次多項式からなる生成関数を考える:

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

BOPのFITの総和を求めよ.