$\newcommand{\ds}{\displaystyle}$ $\newcommand{\fp}[2]{#1^{\underline{#2}}}$ $\newcommand{\sns}[2]{\genfrac{\{}{\}}{0pt}{0}{#1}{#2}}$ $\newcommand{\mbf}{\mathbf}$
A sequence $a_0, a_1, a_2, \ldots$ is polynomial (of degree $d$) if there is a polynomial $P(x)$ (of degree $d$) such that
$$a_n = P(n) \qquad \text{for each}\ n \ge 0.$$In that case, we say that $P(x)$ represents $(a_n)$.
A polynomial sequence of degree $0$ precisely is a nonzero constant sequence.
If $P$ and $Q$ are polynomials representing $a$, then
$$(P-Q)(n) = P(n)-Q(n) = a_n-a_n = 0$$for all $n$. Thus, $P-Q$ is a polynomial with infinitely many zeros and hence must be the zero polynomial, i.e. $P = Q$.
So a polynomial sequence is represented by a unique polynomial.
Example. Fix $d \ge 0$,
The sequence $1^d, 2^d, 3^d, \ldots n^d \ldots $ is polynomial of degree-$d$
The sequence $(P(n,d))_n$ is represented by $x$ to the falling $d$:
So $P(n,d)$ is polynomial of degree $d$. Also is $\displaystyle \binom{n}{d} = \frac{P(n,d)}{d!}=\frac{\fp{n}{d}}{d!}$.
$\ds \binom{n}{0}=1 = n^0$ is the constant sequence $1,1,1,1...$
$\ds \binom{n+1}{1}=n+1 : 1,2,3,4, \ldots$.
There are two fundamental questions concering polynomial sequences:
We define two operators on functions $f$ having the property that $f(x+1)$ is defined whenever $f(x)$ is:
The forward unit push operator $S$: $$(Sf)(x) = f(x+1)$$
The (forward) difference operator $\Delta$:
$\Delta^0 :=\mathbf{1}$ is the identity operator, i.e. $\Delta^0 f = f$ and
$$(\Delta f)(x) =f(x+1)-f(x).$$For $k \ge 1$, define $\Delta^k$ to be $\Delta \Delta^{k-1}$.
So, $\Delta = S - \mathbf{1}$. In other words, $S = \mathbf{1} + \Delta$.
Examples.
$Sx^2 = (x+1)^2 = x^2 + 2x +1$.
$\Delta x^2 = (x+1)^2 - x^2 = 2x+1$. More generally, $\Delta x^d = (x+1)^d - x^d$ is a degree $d-1$ polynomial.
A sequence $(a_n)$ is a function of $n$, so for a fixed $k$, $\ds S\binom{n}{k} = \binom{n+1}{k}$ and $\ds \Delta \binom{n}{k} = \binom{n+1}{k} - \binom{n}{k} = \binom{n}{k-1}.$
$S\fp{x}{3} = \fp{(x+1)}{3} = (x+1)x(x-1)$. So
\begin{align*} \Delta \fp{x}{3} &= \fp{(x+1)}{3}-\fp{x}{3} = (x+1)x(x-1) - x(x-1)(x-2)\\ &=x(x-1)(x+1-x+2) = 3x(x-1) = 3\fp{x}{2}. \end{align*}More generally, $\Delta\fp{x}{d} = d\fp{x}{d-1}$.
Note the similarity between $\Delta$ and the differential operator $D:=d/dx$. For example,
$\Delta$ is also linear, i.e.
$$\Delta(cf(x) + g(x)) = c\Delta f(x) + \Delta g(x)$$for any constant $c$ and function $f,g$.
In view of (4) in the previous example, the falling powers $\fp{x}{d}$ plays the same role (with respect to $\Delta$) as the ordinary powers $x^d$ with respect to $D$.
It follows easily from linearlity of $\Delta$ and the 2nd example above that for any polynomial $P$,
$$\deg \Delta P = \deg P -1.$$Consequently, for a non-zero polynomial $P$, $d = \deg P$ if and only if $d \ge 0$ is the least integer such that $\Delta^{d+1} P = 0$ .
Theorem (Discrete Taylor's Theorem) For any $n \ge 0$,
$$ f(c+n) = \sum_{k=0}^{\infty} \frac{\Delta^k f(c)}{k!} \fp{n}{k} \tag{1}$$It follows from the binomial theorem that
$$ (S^nf) = ((1+\Delta)^n f) = \sum_{k=0}^n \binom{n}{k}\Delta^k f = \sum_{k=0}^{\infty} \frac{\Delta^k f}{k!} \fp{n}{k}. \tag{2}$$The last equality holds because $\fp{n}{k}=0$ for $k > n$.
Equation $(1)$ now follows by evaluating both sides of $(2)$ at $c$.
Corollay 1. If $f$ is a polynomial then
$$ f(x) = \sum_{k=0}^d \binom{x}{k} \Delta^k f(0) = \sum_{k=0}^d \frac{\Delta^k f(0)}{k!} \fp{x}{k} \tag{3}$$where $d$ is the degree of $f$
Proof. Apply the Discrete Taylor's Theorem to the polynomial $f$ at $c=0$, then for each $n$,
$$ f(n) = \sum_{k=0}^{\infty} \frac{\Delta^k f(0)}{k!} \fp{n}{k} = \sum_{k=0}^d \frac{\Delta^k f(0)}{k!} \fp{n}{k}.$$Then last equality holds because $\Delta^k f \equiv 0$ for $k > d= \deg f$. So, Equation (3) follows as the two polynomials involved agree at infinitely many points.
Proposition 1. A sequence $a$ is polynomial of degree $d \ge 1$ if and only if $\Delta a$ is polynomial of degree $d-1$.
Proof. If $a$ is represent by a polynomial $P$ of degree $d$, then $\Delta a$ is represented by the polynomial $\Delta P$ a degree $d-1$ polynomial.
Conversely, if $\Delta a$ is represented by a polynomial $Q(x)$ of degree $d-1$, then, according to Corollary 1, we can write
$$Q(x) = \sum^{d-1}_{k=0} c_k \fp{x}{k},\qquad (c_{d-1} \neq 0). $$We claim that the sequence $a$ is represented by the polynomial
$$P(x) = a_0 + \sum^{d-1}_{k=0} c_k \fp{x}{k+1}$$The that the leading term of $P$ is $(c_{d-1}/d!) x^d$. Since $c_{d-1} \neq 0$, so $P$ has degree $d$. To see that $P(x)$ represents $a$, note that $\Delta P = Q$, $P(0) = a_0$ and
$$ P(n)-P(0) = \sum_{k=0}^{n-1} (\Delta P)(k) = \sum_{k=0}^{n-1} Q(k) = \sum_{k=0}^{n-1} (\Delta a)_k = a_n - a_0.$$Therefore, $P(n) =a_n$ for all $n \ge 0$.
Corollary 2. A nonzero sequence $(a_n)$ is polynomial of degree $d$ if and only if $d$ is the least integer so that $\Delta^{d+1} a$ is the zero sequence.
Moreover, in that case $(a_n)$ is represented by the polynomial $$\sum_{k=0}^d \binom{x}{k}(\Delta^k a)_0 =\sum_{k=0}^d \frac{(\Delta^k a)_0}{k!} \fp{x}{k}.$$
Proof. If $(a_n)$ is represented by a polynomial $f(x)$ of degree $d$, then $\Delta^d a$ is the constant polynomial $\Delta^d f(0)$. And this constant is non-zero, otherwise $\deg(f)$ will be less than $d$ according to Corollary 1. Since $\Delta^d a$ is a constant sequence and so $\Delta^{d+1}a$ is constantly zero.
Conversely, if $d \ge 0$ is the least integer so that $\Delta^{d+1} a$ is constantly zero. Then $\Delta^d a$ must be a nonzero constant sequence, i.e. polynomial of degree $1$. Then $(a_n)$ is polynomial of degree $d$ according to Proposition 1.
Example. Consider the sequence $h$ that begins with:
$$ \mathbf{0},1, 6, 15, 28, 45, 66, 91, 120, 153,\ldots $$Then $(\Delta h)$ begins with:
$$ \mathbf{1}, 5, 9, 13, 17, 21, 25, 29, 33,\ldots $$And $\Delta^2 h$ is the constant sequence $\mathbf{4},4,4,4,4,4, \ldots$.
Here the $(\Delta^i a)_0$ ($i=0,1,2)$ are bold-faced.
Thus, $h$ is $\Delta^2$-constant and hence, according to Corollary 2, is represented by
$$ \begin{align*} &(\Delta^2 a)_0 \binom{x}{2} + (\Delta a)_0 \binom{x}{1} + (\Delta^0 a)_0 \binom{x}{0} \\ &= \mathbf{4}\binom{x}{2} + \mathbf{1}\binom{x}{1} + \mathbf{0}\binom{x}{0} \\ &= 4\frac{x(x-1)}{2} + x = 2(x^2 -x) + x = 2x^2 -x = x(2x-1). \end{align*} $$N.B. $h_n$ is the $n$-hexgonal number.
Exercise. Find the polynomial that represents the sequence
$$ s_n = 1^3 + 3^3 + 5^3 + \cdots + (2n+1)^3 $$Let us apply what we have learned to the powers of $x$.
According to the Theorem
$$ x^n = \sum_{k=0}^n \frac{(\Delta^k x^n)(0)}{k!} \fp{x}{k}$$Note that
\begin{align*} \Delta^k x^n &= (S-\mathbf{1})^k x^n = \sum_{j=0}^k (-1)^j \binom{k}{j} S^{k-j} x^n = \sum_{j=0}^k (-1)^j\binom{k}{j}(x+k-j)^n \end{align*}So we have
$$ x^n = \sum^n_{k=0} \sum_{j=0}^k (-1)^j \binom{k}{j}\frac{(k-j)^n}{k!} \fp{x}{k}$$We claim that
$$ \sum_{j=0}^k (-1)^j \binom{k}{j}\frac{(k-j)^n}{k!} = \sns{n}{k}$$where $\sns{n}{k}$ is the number of partitions of $[n]$ with $k$ parts. (i.e. a Stirling number of the second kind)
It suffices to show that for each $m$,
$$ m^n = \sum_{k=0}^n \sns{n}{k}\fp{m}{k} $$To see that note that $m^n$ counts the number of functions from $[n]$ to $[m]$.
Let $f$ be a function from $[m]$ to $[n]$ whose range has $1 \le k \le m$ elements.
It is clear that such a function is completely determined by its fibres which form a partition of $[n]$ with $k$ parts and where each fibre maps to (so an injective map from $[k]$ to $[m]$)
In other words, the number $\sns{n}{k}\fp{m}{k}$ counts the number of functions from $[n]$ to $[m]$ whose range is of size $k$.
This completes the proof.