9
$\begingroup$

This question already has an answer here:

Given integers $x_1, x_2, \dotsc, x_n$, prove that the expression $$ \prod \limits_{1\leq i<j\leq n}\frac{x_i - x_j}{i-j} $$ is always an integer.

I think induction should work, but I couldn't get anywhere with it.

$\endgroup$

marked as duplicate by user186170, user147263, hardmath, Dan, Fly by Night Sep 4 '15 at 23:11

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ This is false. For $x_1 = x_2 = 1$ and $x_3 = 2$ the sum is $3/2$. $\endgroup$ – vonbrand Sep 4 '15 at 19:24
  • 2
    $\begingroup$ @vonbrand: No, if $x_i$ are not distinct, the product is trivially 0. $\endgroup$ – Alex R. Sep 4 '15 at 19:24
  • 1
    $\begingroup$ @AlexR., brain malfunction. Saw $\sum$. $\endgroup$ – vonbrand Sep 4 '15 at 19:33
  • 1
    $\begingroup$ A slight trick is needed to reduce this problem to the earlier one, which concerns on the face positive integers. However the trick is the obvious one: since only differences $x_i - x_j$ are present, the expression remains the same when a large positive constant is added to all the variables. $\endgroup$ – hardmath Sep 4 '15 at 22:15
  • $\begingroup$ Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level. $\endgroup$ – Fly by Night Sep 4 '15 at 23:10
4
$\begingroup$

I don't know of a really easy of proving this fact, but here is one possible proof. The product $\prod_{1\leq i<j\leq n}(i-j)=\prod_{i=1}^ni!$ is a super factorial. The idea is that $\prod_{1\leq i<j\leq n}(x_i-x_j)$ is a vandermonde determinant, i.e. a determinate of the matrix:

$$\begin{pmatrix} 1 & x_1 & x_1^2\cdots & x_1^{n-1}\\ 1 & x_2 & x_2^2\cdots & x_2^{n-1}\\ \vdots & \vdots & \vdots & \vdots\\ 1 & x_n & x_n^2\cdots & x_n^{n-1} \end{pmatrix}.$$

The key is that by applying column operations to the above matrix, we can transform it the determinant of:

$$\begin{pmatrix} 1 & p_1(x_1) & p_2(x_1)\cdots & p_{n-1}(x_1)\\ 1& p_1(x_2) & p_2(x_2)\cdots & p_{n-1}(x_2)\\ \vdots & \vdots & \vdots & \vdots\\ 1 & p_1(x_n) & p_2(x_n)\cdots & p_{n-1}(x_n) \end{pmatrix},$$

where $p_i(x)$ is any collection of polynomials that are monic (having leading coefficient 1). In this case you can choose $p_i(x)=x(x-1)\cdots (x-i+1)=\binom{x}{i}i!$. Thus the product $\prod_{i=1}^ni!$ factors out and you're left with a determinant of binomial coefficients, which is an integer.

$\endgroup$
  • $\begingroup$ IMO this is a cool approach. May be something simpler is out there but anyway... $\endgroup$ – Jyrki Lahtonen Sep 4 '15 at 19:48

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