$f(z+1)-f(z)$ is a polynomial map, then $f(z)$ is a polynomial map Let $f: \mathbb{Z}\rightarrow\mathbb{Z}$ be a map of sets, if the map $f(z+1)-f(z)$ can be written as some polynomial of $z$ with $\mathbb{Q}$-coefficients, then $f(z)$ can be also written as a polynomial of $z$ with $\mathbb{Q}$-coefficients.
How to prove this?
Thanks in advance.
 A: (The statement is true even for $ f: \mathbb{Z} \rightarrow \mathbb{Q} $, which should make sense because we could multiply by the LCM of the denominator.)
Set up the difference table where $ D_0 (z) = f(z) $ and $ D_{i+1} (z) = D_{i} (z+1) - D_{i} (z)$ for $ i \geq 0$.
We are given that $D_i(z)$ are rational for $i\geq 1$.
Claim: $$ f(x) = f(1) + \sum_{i=1}^{n+1} \frac{ D_i (1) }{i!} \times f_i (x),$$ where $f_i(x) = (x-1) \times (x-2) \times \ldots \times (x-i)$ are polynomials.
Proof: Refer to Method of Differences for polynomial interpolation.
Hence, $ f(x)$ is indeed a rational polynomial.

As an alternative but equivalent interpretation,
(Fill in the gaps, if any. If you're stuck, show your work and explain what you have tried.)
Define $ f_i (x) = (x-1) (x-2) \ldots (x-i)$ for $ i \geq 1$, which is a polynomial of degree $i$.
Observe that $f_{i+1} (x+1) - f_{i+1} (x) = i f_{i} (x)$ for $ i \geq 1$.
Observe that $ f_i (1) = 0 $ for $ i \geq 1$.
Claim: There exists a representation
$$f(x+1) - f(x) = \sum a_i f_i (x),$$
where $a_i$ are rational numbers.
Sketch of Proof: Work from the highest degree on the LHS downwards, to obtain such a representation.
Note: The RHS are polynomials of degree $i$ which are linearly independent, so the representation is unique.
Corollary: $f(x+1) - f(x) = \sum a_i f_i (x) = \sum \frac{a_i}{i} \left[ f_i (x+1) - f_i (x) \right]$, so we can obtain the representation $ f(x) = \left[ \sum \frac{a_i}{i} f_i (x) \right] + C$, for some constant $C$.
Substituting $ x = 1$, we get $ C = f(1)$.
This gives us our rational polynomial representation.
