Polynomial in $\mathbb{Q}[x]$ sending integers to integers? 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.
 A: 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 \dbinom{x}{0}$, 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\limits_{i=0}^{m-1} (a_i/b_i) x^i$. Since the polynomial $b_m f(x) - a_m m! \dbinom{x}{m}$ 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! \dbinom{x}{m}
= 
\sum_{j=0}^{m-1} c_j \dbinom{x}{j}, \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! \dbinom{x}{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! \dbinom{x}{m}
+
\frac{1}{b_m} \sum\limits_{j=0}^{m-1} c_j \dbinom{x}{j}, \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} \dbinom{k}{j}
$$
and since the first $k$ terms of the sum are integers, $c_k/b_m$ must also be an integer and 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,
A: 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.
A: 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.
