I have seen this statement in different variants, but could not find a proof:
If the $n$-th order differences of equally spaced data are non-zero and constant then the data can be represented by a polynomial.
I interpret this statement more formally as follows:
Let $f \colon \mathbb{Z} \to \mathbb{Z}$ be any function such that the finite differences $D_r$, defined by
$D_{r+1}(x) = D_r(x+1)-D_r(x)$ for $r \geq0$ (where $D_0 := f$ by convention)
are such that $D_r$ is constant and non-zero for any $r\geq r_0$. Then $f$ is a polynomial in $x$ (with $\mathbb{Q}$ coefficients) and degree $r_0$.
Question: Is this correct as I stated it? How does one prove that such $f$ must be a polynomial?
Every polynomial of degree $d$ can be expressed in the basis given by the Falling Factorials up to falling index $d$.
That is $$ \eqalign{ & p(x) = a_{\,d} \,x^{\,d} + a_{\,d - 1} \,x^{\,d - 1} + \; \cdots \; + a_{\,0} \,x^{\,0} = \cr & = b_{\,d} \,x^{\,\underline d } + b_{\,d - 1} \,x^{\,\underline {d - 1} } + \; \cdots \; + b_{\,0} \,x^{\,\underline 0 } \cr} $$
Then, from the properties of the falling factorial, it is easy to demonstrate that $$ \Delta ^n p(0) = \sum\limits_k {\left( { - 1} \right)^{n - k} \left( \matrix{ n \cr k \cr} \right)\;p(k)} = \left\{ {\matrix{ 0 & {d < n} \cr {d!b_{\,d} = d!a_{\,d} } & {n = d} \cr {n!b_{\,n} } & {n \le d} \cr } } \right. $$
And viceversa, given $$ \Delta ^d p(x) = d!b_{\,d} \quad \Rightarrow \quad \Delta ^{d + 1} p(x) = 0 $$ the Newton series assures us that $$ p(a + x) = p(a) + x\,\Delta p(a) + \cdots + {{x^{\,\underline {\,d} } } \over {d!}}\;\Delta ^{\,d} p(a) $$
So we can conclude that
if we are given a sequence of $m+1$ points equally spaced by $h$ $$ \left\{ {x_0 ,x_0 + h,x_0 + 2h, \ldots ,x_0 + mh} \right\} $$ and the corresponding sequence of values taken by a function $f(x)$ $$ \left\{ {f(x_0 + kh)} \right\}_{k = 0}^h $$ we can put $$ f\left( {x_0 + kh} \right) = f\left( {h\left( {{{x_0 } \over h} + k} \right)} \right) = g\left( k \right) $$
denoting the differences as $$ \left\{ \matrix{ \Delta g\left( k \right) = g\left( {k + 1} \right) - g\left( k \right) \hfill \cr \Delta ^n g\left( k \right) = \Delta \left( {\Delta ^{n - 1} g\left( k \right)} \right) = \hfill \cr = \sum\limits_{\left( {0 \le } \right)j\left( { \le n} \right)} {\left( { - 1} \right)^{n - j} \left( \matrix{ n \cr j \cr} \right) g\left( {k + j} \right)} \quad \left| {\;0 \le n + k \le m} \right. \hfill \cr} \right. $$ we have that the sequence in $n$ of $ (-1)^n \Delta ^n g\left( k \right)$ is the Binomial Transform of the sequence of the values $g(k+n)$ $$ \left\{ {\left( { - 1} \right)^n \Delta ^n g\left( k \right)} \right\}_{n = 0}^{m - k} \mathrel{\mathop{\kern0pt\longleftrightarrow} \limits_{Binomial\;Transform}} \left\{ {g\left( {k + n} \right)} \right\}_{n = 0}^{m - k} $$ and since the Binomial Transform is self-inverse, we get $$ g\left( {k + n} \right) = \sum\limits_{\left( {0 \le } \right)j\left( { \le n} \right)} {\left( \matrix{ n \cr j \cr} \right)\Delta ^j g\left( k \right)} = \sum\limits_{\left( {0 \le } \right)j\left( { \le n} \right)} {{{\Delta ^j g\left( k \right)} \over {j!}}\left( {\left( {n + k} \right) - k} \right)^{\underline {\,j\,} } } $$ which is precisely the Newton series.
given $n+1$ points $\{k, k+1, \ldots , k+n\}$ and the respective $g(k+j)$
the Newton series is the unique polynomial of max degree $n$ which interpolates them.
if the differences of order $n<m$ are all equal to each other (at changing $k$) $$ \Delta ^n g\left( k \right) = c \ne 0 \quad \left| {\;0 \le \forall k \le m - n} \right. $$ then all the differences of order higher than $n$ will be null $$ \Delta ^{n + q} g\left( k \right) = \Delta ^q \left( {\Delta ^n g\left( k \right)} \right) = \Delta ^q c = 0\quad \left| {\;\forall k} \right. $$ and the relevant Newton series will be the unique polynomial of degree $n$ which interpolates all the $m+1$ points