Prove coefficients are half an integer

Question

Let $f(x)$ be a polynomial of degree at most $2$ with rational coefficients. Suppose $f(n)$ is an integer for every integer $n$. Show that each coefficients of $f(x)$ is half of an integer.

Need help on how to start.

Answer 1

Lets look at $(\Delta f)(x)=f(x+1)-f(x)$. This is a polynomial of degree at most 1. Can you finish the proof?

In fact this works much more generally and is about the representation of functions of polynomial type -- i.e. ones that are defined on the integers and agree with a polynomial of some degree for large enough integers. It is related to Hilbert functions and treatment can be found in almost any intro book on algebraic geometry or commutative algebra.

Here is the actual proof. If $f(x)=ax^2+bx+c$, then $\Delta f(x)=2ax+a+b$ and $a,b\in\mathbb{Q}$. Since $f(x)$ and $f(x+1)$ are integers, so is $\Delta f(x)$, so $2a$ can easily be shown to be an integer (if it bothers you, go one step further, to $\Delta\Delta f$). It follows that $a$ and a fortiori $b$ must be half-integers.

Answer 2

Hint $\ $ Write $\displaystyle\ f(x)\, =\, c_0 + c_1 {x \choose 1} + c_2 {x \choose 2},\ $ possible since $\displaystyle {x\choose k}\,$ has degree $k.\,$ Then

$$\begin{eqnarray} f(0) &=& c_0 \\ f(1) &=& c_0 + {1\choose 1} c_1 \\ f(2) &=& c_0 + {2\choose 1} c_1 + {2\choose 2} c_2 \end{eqnarray}\qquad $$

Successively solving the above for $\,c_0,\ c_1,\ c_2\,$ shows that all $\,c_i\in \Bbb Z,\,$ since all $\,f(i),\, {j\choose k}\in \Bbb Z.$

Remark $\ $ Conversely, if all $\,c_i\in \Bbb Z\,$ then $\,f(n)\in \Bbb Z\,$ since all $\,{x \choose i}\,$ are integer valued.

Thus $\,f(x)\,$ is integer-valued $\iff$ its coefficients in a binomial basis are all integers.

Clearly the same proof works for polynomial of any degree. This is a well-known result of Polya and Ostrowski.