# Prove coefficients are half an integer

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.

• What have you tried so far? For instance, you can write down all polynomials of degree $\leq 2$; have you tried working with any explicit examples? Commented Feb 24, 2015 at 16:47
• I tried writing the general case of f(n)= (a/b)n^2+(c/d)n+(e/f)=m Commented Feb 24, 2015 at 16:58

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.

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.