An integer-valued polynomial is a polynomial $p(x)$ such that $\forall x \in \mathbb{Z}, p(x) \in \mathbb{Z}$.


Theorem: For any $n$-degree polynomial $p$, if $p(x) \in \mathbb{Z}$ for all $x \in \{0, 1, ..., n\}$, then $p$ is an integer-valued polynomial.


The proof is pretty simple for $n = 0, 1$


I have a proof for $n = 2$ and a sketch of the proof for $n = 3$


Is this provable for arbitrary $n$ or is there a counterexample?




---


Possibly relevant: A polynomial $p$ of degree $n$ can be uniquely identified by the numbers $a\_0, a\_1, a\_2, ... a\_n$ where the polynomial is $a\_0\*x^n + a\_1\*x^(n-1) + a\_2\*x^(n-2) ... + a\_n$. The same polynomial can be uniquely identified by the numbers $b\_0, b\_1, b\_2, ... b\_n$ where $p(0) = b\_0, p(1) = b\_1, ... p(n) = b\_n$, as these create a set of $n+1$ linear equations comprised of the $n+1$ variables $a\_0$ through $a\_n$, thus uniquely generating $a\_0$ through $a\_n$.



Integer-valuedness of a polynomial determined by output of first n integers?
This follows from the calculus of finite differences (see, for example, the eponymous book). 


If you start with a n'th degree polynomial p(x) evaluated at n+1 consecutive integers, and then take the 1st differences, then differences of those (i.e., 2nd differences), and so forth, up to the n'th differences, you will get a constant c. If p(x) evaluated at those integers are all integers, then so are the differences of all orders. Once you have this c, you can find the next value of the (n-1)th difference, (n-2)th, and so forth by summing, leading to p(x) at the next integer, which is evidently an integer.


For example, evaluate p(x) = x^2 at 0, 1, 2 obtaining 1 4 9. First differences are 3 5. Second differences gives the constant 2. So the next term of the first differences is 5+2 = 7, and the next term of p(x) (evaluated at 3) is 7+9 = 16. 


