Dada una secuencia $a = \langle a_n \rangle_n$, definir la diferencia secuencia $\Delta a = \langle \Delta a_n \rangle$ donde $\Delta a_n = a_{n+1} - a_n$. Definir $\Delta^2 a = \Delta(\Delta a)$, $\Delta^3 a = \Delta(\Delta^2 a)$, y así sucesivamente. Su ejemplo muestra $a$, $\Delta a$, $\Delta^2 a$, $\Delta^3 a$, y $\Delta^4 a$, por ejemplo. No es demasiado duro para demostrar que si cada una de las $a_n = p(n)$ para algunos un polinomio $p$ grado $d$, entonces no es un polinomio $p_1$ grado $d-1$ de manera tal que cada una de las $\Delta a_n = p_1(n)$. Por inducción se sigue que, para $k = 1,\dots,d$ no es un polinomio $p_k$ grado $d-k$ de manera tal que cada una de las $\Delta^k a_n = p_k(n)$. En particular, $q_d$ es de grado $0$ y por lo tanto es constante, y $\Delta^{d+1} a_n = 0$ todos los $n$.
Resulta que lo contrario también es cierto: si existe un entero no negativo, $d$ tal que $\Delta^{d+1} a_n = 0$ todos los $n$, entonces no es un polinomio $p$ grado $d$ de manera tal que cada una de las $a_n = p(n)$. Esto está demostrado por el hecho de construir un polinomio: resulta que $p(n) = \sum \limits_{k=0}^d (\Delta^k a_0) {n \choose k}$ (donde $\Delta^0 a = a$). Este es el resultado que se utilizó para obtener la fórmula para $S(n)$ en tu ejemplo (salvo que el coeficiente de ${n \choose 3}$ debe $2$). (Puede no ser inmediatamente obvio que esto es realmente un polinomio en $n$. Para ver esto, sólo tenga en cuenta que ${n \choose k} = \frac{1}{k!} n(n-1)\dots(n-k+1)$, lo que claramente es un polinomio en a $n$ grado $k$.)
La prueba de este resultado es un poco largo, pero no es particularmente difícil. Hay una idea muy clara de tratamiento en Edward Scheinerman, Matemáticas: Una Discreta Introducción, 2ª edición, la Sección 22.
