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

Question

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.

Answer 1

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.

Answer 2

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)$.)

Answer 3

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!$).