# Integer-valuedness of a polynomial determined by output of first n integers? [closed]

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$.

• This is not a research level question, so I would suggest asking it at math.stackexchange instead: math.stackexchange.com About the question itself: The statement is true for any $n$. Use induction and the "derivative" $\Delta p(x)=p(x+1)-p(x)$. – Joonas Ilmavirta Nov 12 '14 at 19:37

## 1 Answer

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.