Given a sequence $a = \langle a_n \rangle_n$, define the difference sequence $\Delta a = \langle \Delta a_n \rangle$, where $\Delta a_n = a_{n+1} - a_n$. Define $\Delta^2 a = \Delta(\Delta a)$, $\Delta^3 a = \Delta(\Delta^2 a)$, and so on. Your example shows $a$, $\Delta a$, $\Delta^2 a$, $\Delta^3 a$, and $\Delta^4 a$, for instance. It's not too hard to prove that if each $a_n = p(n)$ for some a polynomial $p$ of degree $d$, then there is a polynomial $p_1$ of degree $d-1$ such that each $\Delta a_n = p_1(n)$. By induction it follows that for $k = 1,\dots,d$ there is a polynomial $p_k$ of degree $d-k$ such that each $\Delta^k a_n = p_k(n)$. In particular, $q_d$ is of degree $0$ and is therefore constant, and $\Delta^{d+1} a_n = 0$ for all $n$.
It turns out that the converse is also true: if there is a non-negative integer $d$ such that $\Delta^{d+1} a_n = 0$ for all $n$, then there is a polynomial $p$ of degree $d$ such that each $a_n = p(n)$. This is proved by actually constructing such a polynomial: it turns out that $p(n) = \sum \limits_{k=0}^d (\Delta^k a_0) {n \choose k}$ (where $\Delta^0 a = a$). This is the result that was used to get the formula for $S(n)$ in your example (except that the coefficient of ${n \choose 3}$ should be $2$). (It may not be immediately obvious that this is actually a polynomial in $n$. To see this, just note that ${n \choose k} = \frac{1}{k!} n(n-1)\dots(n-k+1)$, which is clearly a polynomial in $n$ of degree $k$.)
The proof of this result is a bit long, but it's not particularly difficult. There's a very clear treatment in Edward Scheinerman, Mathematics: A Discrete Introduction, 2nd edition, Section 22.
