How to find all polynomials that map integers to integers?
How can one find all polynomials of degree k that map integers to integers? In other words, how to get all combinations of coefficients
$a_0,...,a_k \in \Bbb R$
sucht that
$n \in \Bbb Z \implies p_k(n) = \sum _{i=0}^{k} a_i n^i \in \Bbb Z$
?
For example $(n^2 + n)/2$ maps integers to integers and I think
$\{ p_2(n) \space | \space n \in \Bbb Z \implies p_2(n) \in \Bbb Z \} = \{q(n^2+2rn)/2 \space | \space q,r \in \Bbb Z\}$
Solution 1:
Also $n\mapsto \binom{n}k$ is integer valued for each $k$, and so is any integer linear combination of these: $\sum_{k=0}^m a_k\binom{n}k$. Indeed these are all the integer-valued polynomials. The key to proving this is to note that if $f$ is integer-valued, then $n\mapsto f(n+1)-f(n)$ is also integer-valued.
Solution 2:
Hint. A polynomial $P(x)$ always takes integer value iff
- $P(0) \in \Bbb{Z}$.
- $Q(x)$ always takes integer value, where $Q(x) = P(x) - P(x-1)$.