Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

We can view the binomial coefficient $\binom{x}{k}$ has a polynomial in $x$ with degree $k$. So taking some $f\in\mathbb{Q}[x]$, why is $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$, precisely when the coefficients of $f$ are integers with respect to the basis $\{\binom{x}{k}\mid k\in\mathbb{N}\}$?

The reverse direction seems clear, so I wonder why the opposite implication is also true. I did notice that all the roots of $\binom{x}{k}$ are just $0,\dots,k-1$. Can we factor the polynomial is some nice way to reveal the opposite conclusion? Thanks.

share|cite|improve this question
The key word here is finite differences. See Newton series. – lhf Feb 12 '12 at 1:58
up vote 12 down vote accepted

This is a special case of a classical result of Polya and Ostrowski (1920): $f(x) \in \mathbb Q[x]$ is an integer valued polynomial, i.e. $f(\mathbb Z)\subset \mathbb Z\:,\:$ iff $f(x)$ is an integral linear combination of binomial coefficients ${x\choose k},\:$ for $\: k\le \deg f$. For a proof see e.g. Polya And Szego, Problems and theorems in analysis, vol II, Problem 85 p. 129 and its solution on p. 320.

For example

$$\rm\displaystyle\ \ \frac{n^3+5\:n}6\ =\ \frac{n^3-n + 6\:n}6\ =\ \frac{(n+1)\:n\:(n-1)}6 + \:n\ =\ {n+1\choose 3} + {n\choose 1}$$

This has been extended to much more general rings (e.g. Dedekind domains) by Cahen at al.

share|cite|improve this answer
Thanks for the reference! – Jacqueline Pauwels Feb 11 '12 at 23:02
This result also appears in LeVeque's Fundamentals of Number Theory, section 3.4, exercise 14. – lhf Feb 12 '12 at 23:35

The idea is simple ; given a polynomial $f \in \mathbb Q[x]$ of degree $m$, we can reduce the degree of $f$ and use induction as in the following :

If a polynomial of degree $0$ is integer-valued, then we can write it as $f(x) = a \in \mathbb Z$ and thus $f(x) = a \begin{pmatrix} x \\\ 0 \end{pmatrix}$ so for $m=0$ we are doing just fine.

Assuming all polynomials of degree $<m$ can be written as such combinations of binomial coefficients, let $f(x) \in \mathbb Q[x]$ be such a polynomial of degree $m$. Then $f(x) = (a_m/b_m) x^m + \sum_{i=0}^{m-1} (a_i/b_i) x^i$. Since $b_m f(x) - a_m m! \begin{pmatrix} x \\\ m \end{pmatrix}$ is also integer valued by assumption, and its degree is at most $m-1$, it can be expressed as $$ b_m f(x) - a_m m! \begin{pmatrix} x \\\ m \end{pmatrix} = \sum_{j=0}^{m-1} c_j \begin{pmatrix} x \\\ j \end{pmatrix}, \qquad c_j \in \mathbb Z $$ without excluding the case where $c_j = 0$ for $0 \le j \le m-1$ (in this case the degree of $b_m f(x) - a_m m!$ is either not defined or $-\infty$ depending on which convention you like, but either way things work out nicely), which means $$ f(x) = \frac{a_m}{b_m} m! \begin{pmatrix} x \\\ m \end{pmatrix} + \frac{\sum_{j=0}^{m-1} c_j \begin{pmatrix} x \\\ j \end{pmatrix}}{b_m}, \qquad c_j \in \mathbb Z $$ Here by computing $f(0)$, $f(1)$, $\dots$, $f(m)$, one can see that this expression is an integer-linear-combination of the binomial coefficients. For instance, $f(0) = c_0 / b_m$, hence $b_m$ divides $c_0$. Then $f(1) = c_1/ b_m + c_0/b_m$, so that $c_1 /b_m$ is an integer, hence $b_m$ divides $c_1$. Going on like this, $$ f(k) = \sum_{j=0}^k \frac {c_j}{b_m} \begin{pmatrix} k \\\ j \end{pmatrix} $$ and since the first $k$ terms of the sum are integers, $c_k/b_m$ must also be an integer thus $b_m$ divides $c_k$. By computing $f(m)$ this process stops. In other words, $f(x)$ is expressible as desired. The result follows by induction.

Hope that helps,

share|cite|improve this answer
The idea between the lines is that the integer-valued coefficients form a $\mathbb Z$-module for which the binomial coefficient polynomials form a basis. I implicitly used the basis part to expect unicity and thus reducing the degree by removing one component allowed me to use induction. – Patrick Da Silva Feb 11 '12 at 23:43

Since you already know that the $\binom Xn$ for $n\in\Bbb N$ form a $\Bbb Q$-basis of $\Bbb Q[X]$ (and indeed this is easy to see), the rest of the argument is trivial. Let $P=\sum_nc_n\binom Xn\in\Bbb Q[X]$ be arbitrary, then the value of $P$ at $m\in\Bbb N$ is $c_m+\sum_{i<n}c_i\binom mi$, which must be an integer. Now by immediate induction on $m$, all the coefficients $c_m$ are integer.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.