Polynôme optimal
Énoncé:
Si l'on nous présente les k premiers termes d'une suite, il est impossible de dire avec certitude la valeur du terme suivant, car il existe une infinité de fonctions polynomiales qui peuvent modéliser la suite.
À titre d'exemple, considérons la suite des nombres cubiques. Celle-ci est définie par la fonction génératrice
$u_n = n^3 : 1, 8, 27, 64, 125, 216, \dots$
Supposons que l'on ne nous donne que les deux premiers termes de cette suite. En partant du principe que "le plus simple est le mieux", nous devrions supposer une relation linéaire et prédire que le terme suivant sera $15$ (différence commune $7$). Même si on nous présentait les trois premiers termes, selon le même principe de simplicité, il faudrait supposer une relation quadratique.
Nous définirons $PO(k, n)$ comme étant le $n$ième terme de la fonction génératrice polynomiale optimale pour les $k$ premiers termes d'une suite. Il devrait être clair que $PO(k, n)$ générera avec précision les termes de la suite pour $n \le k$, et potentiellement le premier terme incorrect (PTI) sera $PO(k, k+1)$ ; dans ce cas nous l'appellerons un mauvais PO (MPO).
Comme base, si on nous donne seulement le premier terme de la suite, il serait plus raisonnable de supposer la constance ; c'est-à-dire, pour $n \ge 2$, $OP(1, n) = u_1$.
Par conséquent, nous obtenons les POs suivants pour la suite cubique:
| $PO(k, n)$ | Premiers termes |
|---|---|
| $PO(1, n) = 1$ | $1, \color{red} 1 \color{black}, 1, 1, \dots$ |
| $PO(2, n) = 7n-6$ | $1, 8, \color{red} 15 \color{black}, \dots$ |
| $PO(3, n) = 6n^2-11n+6$ | $1, 8, 27, \color{red} 58 \color{black}, \dots$ |
| $PO(4, n) = n^3$ | $1, 8, 27, 64, 125, \dots$ |
Clairement, aucun MPO n'existe pour $k \ge 4$.
En considérant la somme des PTI générés par les MPO (indiqués en rouge ci-dessus), on obtient $1 + 15 + 58 = 74$.
Considérons la fonction génératrice polynomiale du dixième degré suivante:
$u_n = 1 - n + n^2 - n^3 + n^4 - n^5 + n^6 - n^7 + n^8 - n^9 + n^{10}$.
Trouve la somme des PTI pour les MPO.
Lien du problème originel