# Show that $P_k(X) = \frac{1}{k!} X (X - 1) ... (X - k + 1)$ is an integer-valued polynomial.

For $$k \in \mathbb{N}$$, let $$P_k(X) = \frac{1}{k!} X (X - 1)(X - 2) ... (X - k + 1)$$.

Show that these are integer-valued polynomials, i.e. $$P_k(X) \in \left\{f \in \mathbb{Q}[X] \mid f(\mathbb{Z}) \subset \mathbb{Z}\right\}$$ for all $$k \in \mathbb{N}$$.

I'm struggling to write down a solid proof.

By induction on $$k$$, we get $$P_{k+1}(X) = P_k(X) \frac{X - k}{k + 1}$$, which doesn't really seem to facilitate the problem.

As for a straight-forward proof, I can't generalize the idea behind my thoughts why this should work out.

• Commented Dec 28, 2016 at 1:04

The value of $P_{k}(X)$ for $X = n \ge 0$ is the binomial coefficient $$\binom{n}{k} = \frac{n!}{k! (n - k)!} = \frac{n (n-1) \cdots (n-k+1)}{k (k-1) \cdots 1},$$ which is an integer, as it counts the ways of choosing $k$ objects out of $n$.

For $X = -n < 0$ we have $$\frac{-n (-n-1) \cdots (-n-k+1)}{k (k-1) \cdots 1} = (-1)^{k} \frac{n (n+1) \cdots (n+k-1)}{k (k-1) \cdots 1} =\\= (-1)^{k} \frac{(n+k-1) \cdots (n+1) n}{k (k-1) \cdots 1} =(-1)^{k} \binom{n + k - 1}{k}.$$ (Thanks to @darij grinberg for noticing this omission.)

A brilliant alternative proof that this is an integer is given by Tim Gowers.

• Not quite: the combinatorial interpretation only works for nonnegative integers. Commented Dec 28, 2016 at 8:06
• @darijgrinberg, you are perfectly right, should have been fixed now. Thanks a lot! Commented Dec 28, 2016 at 8:29

Here's the proof (not original) I like:

Let $p_k(n) = \prod_{j=1}^k (n+j-1)$.

Then $k! | p_k(n)$.

The proof involves a double induction, the outer on $k$, the inner on $n$.

Proof.

It is true for $k=1$, since $1 | n$.

Suppose it is true for $k$.

Consider $p_{k+1}(n)$.

I claim that $(k+1)! | p_{k+1}(n)$.

This is true for $n=1$, since $p_{k+1}(1) = (k+1)!$.

Suppose $(k+1)! | p_{k+1}(n)$.

Then

$\begin{array}\\ p_{k+1}(n+1)-p_{k+1}(n) &=\prod_{j=1}^{k+1} (n+1+j-1)-\prod_{j=1}^{k+1} (n+j-1)\\ &=\prod_{j=1}^{k+1} (n+j)-\prod_{j=0}^{k} (n+j)\\ &=(n+k+1)\prod_{j=1}^{k} (n+j)-n\prod_{j=1}^{k} (n+j)\\ &=((n+k+1)-n)\prod_{j=1}^{k} (n+j)\\ &=(k+1)\prod_{j=1}^{k} (n+j)\\ \end{array}$

But (and here's the part I really like), by the induction hypothesis on $k$, $k! | \prod_{j=1}^{k} (n+j)$.

Therefore $(k+1)! | (k+1)\prod_{j=1}^{k} (n+j)$.

By the induction hypothesis on $n$, $(k+1)! |p_{k+1}(n)$.

Therefore $(k+1)!$ divides both $p_{k+1}(n)$ and $(k+1)\prod_{j=1}^{k} (n+j)$, so it divides their sum, which is $p_{k+1}(n+1)$.

And we are done.

Neat!

(Which, as we have just proved, divides $p_{Neat}(n)$.)

• This needs an extra induction step for negative $n$. Commented Dec 28, 2016 at 8:07
• @darijgrinberg Induction is not needed, one simply needs to note the symmetry ${-n\choose k} = (-1)^k {n+k-1\choose k}$ to cover the negative numbers. Commented Dec 28, 2016 at 8:29
• @Winther: That works too, yes. Commented Dec 28, 2016 at 8:34

This is Proposition 3.20 in my Notes on the combinatorial fundamentals of algebra, version of 10 January 2019 (after observing that $$P_k\left(X\right) = \dfrac{1}{k!} X\left(X-1\right)\cdots\left(X-k+1\right) = \dbinom{X}{k}$$).

Notice the necessity of considering the case when the numerator of the binomial coefficient (called $$m$$ in my notes) is negative. Most proofs require this in some way -- both the combinatorial one (since the combinatorial interpretation only handles the nonnegative case) and the induction one (unless you do a separate "induction step down"). Only the half-combinatorial-half-arithmetical proof by Gowers and Dubuque seems to avoid this issue. Of course, one can also derive the negative case from the nonnegative case: If $$u$$ and $$v$$ are two integers satisfying $$u \equiv v \mod k!$$, then $$\dbinom{u}{k}$$ is an integer if and only if $$\dbinom{v}{k}$$ is an integer, and therefore we can always replace an integer $$u$$ by some nonnegative integer $$v$$ that is congruent to $$u$$ modulo $$k!$$ (for example, $$v$$ can be set to be the remainder of $$u$$ modulo $$k!$$).