We present two approaches. First solution (induction and degree counting) We proceed by induction on $n \ge 2$ with the base case being clear. Let $E_n$ be the given expression. For each $n$, imagine clearing all denominators to get the expression \[ F_n = \prod_{i<j} (x_i-x_j) [E_n - (n \bmod 2)] \]which is a polynomial in $x_1$, \dots, $x_n$. Note that \[ \deg F_n = \binom n2 + 2(n-1) - (n-1) = \binom n2 + (n-1). \]However, we make two remarks. Claim: $F_n$ is divisible by $x_i - x_j$ for $i < j$. Proof. It is enough to show $x_1 - x_2$ divides $F_n$ by symmetry. Suppose we fix distinct $x_2, x_3, \dots, x_n$ with $x_2 \ne 1$ and vary $x_1$; then \begin{align*} \lim_{x_1 \to x_2} E_n &= \lim_{x_1 \to x_2} \left( \frac{1-x_1x_2}{x_1-x_2} \prod_{j \ge 3} \frac{1-x_1 x_j}{x_1 - x_j} + \frac{1-x_2x_1}{x_2-x_1} \prod_{j \ge 3} \frac{1-x_2 x_j}{x_2 - x_j} \right) \\ &= (1-x_2^2) \lim_{x_1 \to x_2} \left( \frac{\prod_{j \ge 3} \frac{1-x_1 x_j}{x_1 - x_j} - \prod_{j \ge 3} \frac{1-x_2 x_j}{x_2 - x_j} }{x_1-x_2} \right). \end{align*}As a rational function, the numerator is evidently divisible by $x_1-x_2$ so this limit exists (and is finite). Consequently, it follows that $F_n$ vanishes whenever $x_1 = x_2$. This implies the result. $\blacksquare$ Claim: $F_n$ is divisible by $x_i - 1$ for each $i$. Proof. If $x_n = 1$, then \[ E_n = (-1)^{n-1} E_{n-1} + (-1)^{n-2} \]which by the induction hypothesis is enough to imply $F_n = 0$. $\blacksquare$ Thus if $F_n \ne 0$ we get $\deg F_n \ge \binom n2 + n$, a contradiction. This completes the proof. Second solution using differentiation and partial fractions Replace $x_n$ by $t$ and fix $x_1$, \dots, $x_{n-1}$. We will prove that the expression $E$, as a rational function in $T$, has $\frac{dE}{dt} = 0$. Claim: [Partial fraction decomposition] We have \[ \prod_{i=1}^{n-1} \frac{tx_i-1}{t-x_i} = x_1 \dots x_{n-1} + \sum_{i=1}^{n-1} \frac{(x_i^2-1)\prod_{j \ne i} \frac{x_ix_j-1}{x_i-x_j}}{t-x_i}. \]Proof. Note that $\prod_{j=1}^{n-1} \frac{tx_j-1}{t-x_j} - x_1 \dots x_{n-1}$ is a rational function in $t$ whose numerator has smaller degree than the denominator. Hence it has a unique partial fraction decomposition of the form $\sum \frac{c_j}{t-x_j}$ for $c_j$ independent of $t$. Clearing the denominators and letting $t = x_j$ yields the result. $\blacksquare$ For brevity, define $c_i = \prod_{j \ne i} \frac{1 - x_i x_j}{x_i - x_j}$, so now \[ \prod_{i=1}^{n-1} \frac{tx_i-1}{t-x_i} = x_1 \dots x_{n-1} + \sum_{i=1}^{n-1} \frac{(-1)^{n-1} c_i}{t-x_i}. \]Thus, it follows that \begin{align*} \frac{\partial}{\partial t} \prod_{i=1}^{n-1} \frac{1-tx_i}{t-x_i} &= (-1)^{n-1} \frac{\partial}{\partial t} \left[ x_1 \dots x_{n-1} + \sum_{i=1}^{n-1} (-1)^{n-1} c_i \frac{x_i^2-1}{t-x_i} \right] \\ &= \sum_{i=1}^{n-1} c_i \cdot \frac{\partial}{\partial t} \left[ \frac{x_i^2-1}{t-x_i} \right] = -\sum_{i=1}^{n-1} c_i \frac{x_i^2-1}{(t-x_i)^2}. \end{align*}However by the so-called quotient rule we also have \[ \frac{\partial}{\partial t} \left[ \frac{1-x_i t}{x_i - t} \right] = \frac{(1-x_i t)(-1) - (-x_i)(x_i-t)}{(x_i-t)^2} = \frac{x_i^2-1}{(t-x_i)^2} \]by the so-called quotient rule. Putting this all together gives \begin{align*} \frac{\partial E}{\partial t} &= \frac{\partial}{\partial t} \left[ \sum_{i=1}^n c_i \cdot \frac{1-x_i t}{x_i-t} + \prod_j \frac{1-tx_i}{t-x_i} \right] \\ &= \sum_{i=1}^n c_i \cdot \frac{\partial}{\partial t} \left[ \frac{1-x_i t}{x_i -t} \right] + \frac{\partial}{\partial t} \left[ \prod_j \frac{1-tx_i}{t-x_i} \right] \\ &= \sum_{i=1}^n c_i \cdot \frac{x_i^2-1}{(t-x_i)^2} -\sum_{i=1}^{n-1} c_i \frac{x_i^2-1}{(t-x_i)^2} = 0. \end{align*}Therefore, $E$ is constant in $x_n$ and hence in all $x_i$. To finish, note that if $n = 2k$ is even we may take $x_1 = 10$, $x_2 = 20$, \dots, $x_{k} = 10k$ and $x_{k+1} = 1/10$, $x_{k+2} = 1/20$, \dots, $x_{2k} = 1/(10k)$, so every term in the original sum vanishes. On the other hand if $n = 2k+1$ is odd we add $x_{2k+1} = 1$ and the final term equals $1$ instead.

Here is a solution with Lagrange Interpolation. Note that the term with degree $2k$ of the product $\prod_{j \neq i} (1-x_{i}x_{j})$ will be of the form $\frac{(-x_i)^k \sum_{1 \leqslant i_1<i_2<...<i_k \leqslant n, i_t \neq i} (x_{i_1} x_{i_2} \ldots x_{i_k})}{\prod_{j \neq i}(x_{i}-x_{j})}$. By Lagrange Interpolation, the polynomial $x^k$ is equivalent to $\sum_{1 \leqslant i \leqslant n} x_i^k\prod_{j \neq i} \frac{x-x_j}{x_{i}-x_{j}}$. Therefore, summing $\frac{(-x_i)^k \sum_{1 \leqslant i_1<i_2<...<i_k \leqslant n, i_t \neq i} (x_{i_1} x_{i_2} \ldots x_{i_k})}{\prod_{j \neq i}(x_{i}-x_{j})}$ over all $i$, we get exactly equal to the coefficient of $x^{n-k-1}$ of the polynomial $x^k$. This immediately implies that the desired sum is $0$ if $n$ is even, as $n-k-1=k$ never holds, and $1$ if $n$ is odd, as $n-k-1=k$ for exactly one value of k. Motivation: If we try to expand the numerator and sum each term individually, we find that we need to evaluate the degree $2k$ terms. Since these expressions resemble Interpolation, we wish to try to find a way to use it.

When I saw this problem, I was taking a class that introduces a technique to compute this kind of stuff. Therefore it was an instant kill for me. The following solution basically follows this: http://math.mit.edu/~apost/courses/18.218/lecture25.html

For distinct real numbers $x_1, x_2, \dots, x_n$ define $$f(x_1, x_2, \dots, x_n) := \displaystyle\sum_{i=1}^{n}\displaystyle\prod_{j\neq i}\frac{1-x_ix_j}{x_i-x_j}$$We will use induction on $n$. If $n=2$, then $$f(x_1, x_2) = \frac{1-x_1x_2}{x_1-x_2} + \frac{1-x_2x_1}{x_2-x_1} = \frac{1-x_1x_2}{x_1-x_2} - \frac{1-x_1x_2}{x_1-x_2} = 0$$Suppose the claim is true up to $n$ and let's prove it for $n$. Consider $$g(x_1, x_2, \dots, x_n) = \displaystyle\sum_{i=1}^{n}\displaystyle\prod_{j\neq i}\left(1 + \frac{1-x_ix_j}{x_i-x_j}\right)$$After expanding product on the right hand side we get \begin{align*} g(x_1, x_2, \dots, x_n) &= \displaystyle\sum_{i=1}^{n}\displaystyle\sum_{k=0}^{n-1}\sum_{\substack{s_1, s_2, \dots, s_k\\i\not\in\{s_1, s_2, \dots, s_k\}}}\prod_{j\in \{s_1, s_2, \dots, s_k\}}\frac{1-x_ix_j}{x_i-x_j}\\ &=\displaystyle\sum_{k=0}^{n-1}\displaystyle\sum_{i=1}^{n}\sum_{\substack{s_1, s_2, \dots, s_k\\i\not\in\{s_1, s_2, \dots, s_k\}}}\prod_{j\in \{s_1, s_2, \dots, s_k\}}\frac{1-x_ix_j}{x_i-x_j}\\ &=\displaystyle\sum_{k=0}^{n-1}\displaystyle\sum_{i_1, i_2, \dots, i_{k+1}}f(x_{i_1}, x_{i_2}, \dots, x_{i_{k+1}})\\ \end{align*}Then by induction hypothesis \begin{align*} g(x_1, x_2, \dots, x_n) &= f(x_1, x_2, \dots, x_n) + \displaystyle\sum_{\substack{k=0\\k\text{ even}}}^{n-2}\sum_{i_1, i_2, \dots, i_{k+1}}1 =f(x_1, x_2, \dots, x_n) + \displaystyle\sum_{\substack{k=0\\k\text{ even}}}^{n-2}\binom{n}{k+1}\\ &= f(x_1, x_2, \dots, x_n) + \begin{cases} 2^{n-1},&\text{if }n\text{ is even;}\\ 2^{n-1} - 1,&\text{if }n\text{ is odd.}\\ \end{cases} \end{align*}On the other hand \begin{align*} g(x_1, x_2, \dots, x_n) &= \displaystyle\sum_{i=1}^{n}\displaystyle\prod_{j\neq i}\left(1 + \frac{1-x_ix_j}{x_i-x_j}\right) = \displaystyle\sum_{i=1}^{n}\displaystyle\prod_{j\neq i}\frac{(1 + x_i)(1-x_j)}{x_i-x_j}=\displaystyle\sum_{i=1}^{n}\left((1 + x_i)^{n-1}\displaystyle\prod_{j\neq i}\frac{1-x_j}{x_i-x_j}\right) \end{align*}Using binomial expansion we get \begin{align*} g(x_1, x_2, \dots, x_n) &=\displaystyle\sum_{i=1}^{n}\sum_{r=0}^{n-1}\binom{n-1}{r}x_i^r\displaystyle\prod_{j\neq i}\frac{1-x_j}{x_i-x_j}=\sum_{r=0}^{n-1}\left(\binom{n-1}{r}\displaystyle\sum_{i=1}^{n}\left(x_i^r\displaystyle\prod_{j\neq i}\frac{1-x_j}{x_i-x_j}\right)\right) \end{align*}By Lagrange Interpolation Theorem we know that $$t^r = \displaystyle\sum_{i=1}^{n}\left(x_i^{r}\displaystyle\prod_{j\neq i}\frac{t-x_j}{x_i-x_j}\right)$$for all $0 \leq r \leq n-1$. So by plugging $t=1$ in this identity and using it in above equation we get $$ g(x_1, x_2, \dots, x_n)=\sum_{r=0}^{n-1}\binom{n-1}{r}=2^{n-1}$$Combining this with above equality we get $$f(x_1, x_2, \dots, x_n) = \begin{cases} 0,&\text{if }n\text{ is even;}\\ 1,&\text{if }n\text{ is odd.}\\ \end{cases}$$and this completes our induction.

Comment: I really enjoy this problem. It has a very short statement and elegant solution using a clever Lagrange Interpolation. First we prove the following lemma. Lemma: Let $a_1<a_2<\hdots<a_n$ and $b_1,b_2,\hdots,b_n$ be real numbers. Suppose that there exists polynomial $P$ which $\deg P \leq n-2$ and $P(a_i)=b_i$ for each $i$. Then $$\sum_{i=1}^n b_i\prod_{j\ne i}\frac{1}{a_i-a_j} = 0$$ Proof: By Lagrange interpolation formula, $$P(x) = \sum_{i=1}^n b_i\prod_{j\ne i}\frac{x-a_j}{a_i-a_j}$$so comparing the $x^{n-1}$-coefficient gives the conclusion. $\blacksquare$ Let $P(x) = (x-x_1)(x-x_2)\hdots (x-x_n)$. Assume that $x_1,x_2\hdots,x_n\ne 1,-1$ or otherwise the result follows by continuity. Applying the lemma on polynomial $x^nP\left(\frac 1x\right)$ and points $1,-1,x_1,x_2,\hdots,x_n$, we find \begin{align*} 0 &= \left(\sum_{i=1}^n \frac{x_i^n P\left(\frac{1}{x_i}\right)}{(x_i-1)(x_i+1)} \prod_{j\ne i} \frac{1}{x_i-x_j}\right) + \left(\frac{P(1)}{1-(-1)}\prod_{i=1}^n \frac{1}{1-x_i}\right) \\ &\qquad + \left(\frac{(-1)^nP(-1)}{(-1)-1}\prod_{i=1}^n\frac{1}{(-1)-x_i}\right) \\ &= \left(\sum_{i=1}^n \frac{x_i^n \prod\limits_{k=1}^n \left(\frac{1}{x_i}-x_k\right)}{x_i^2-1} \prod_{j\ne i} \frac{1}{x_i-x_j}\right) + \left(\frac{P(1)}{2}\cdot\frac{1}{P(1)} \right) + \left(\frac{(-1)^nP(-1)}{-2}\cdot\frac{1}{P(-1)}\right) \\ &= \left(\sum_{i=1}^n \frac{\prod\limits_{k=1}^n (1-x_ix_k)}{x_i^2-1} \prod_{j\ne i} \frac{1}{x_i-x_j}\right) + \frac{1-(-1)^n}{2} \\ &= -\left(\sum_{i=1}^n \prod_{j\ne i} \frac{1-x_ix_j}{x_i-x_j}\right) + \frac{1-(-1)^n}{2} \end{align*}which gives the desired result.

After solving the problem, I quickly googled to see if the equivalent result was known, and turns out it was. Not sure how this slipped through. Let $x_i = \coth(a_i)$; the term in the product becomes $\cot(a_i-a_j)$. The result then immediately follows from Hermite's cotangent identity with complex variables. (The identity isn't hard to prove either; just use induction to show that the product of cotangents can be converted into a sum, and then take $z \to a_i$ to get coefficients.) This is the fourth ISL problem this year that could be killed instantly via random theorems (G4, nine-point-conic; G5, Bretschneider; A6, cosine identity; there may be more but these are the ones that I found when solving).

Denote by $F$ the value of the expression in the problem. We will work with the following polynomial : $$P(X) \stackrel {\text {def}}{:=} \prod_{i=1}^n(1-xx_i)$$ Note that $P(x_i) = (1-x_i^2) \textstyle \prod_{j\neq i} (1-x_ix_j)$. We will use Lagrange interpolation on $P(X)$ with the points $x_1,x_2,\dots,x_n,1,-1$. We get the following expression for $P(x)$ := $$P(X) = \sum_{i=1}^n P(x_i)\cdot \frac {(x^2-1)}{(x_i^2-1)} \prod_{j\neq i} \frac {(x-x_j)} {(x_i-x_j)} + \frac {P(1)}{2} (x+1) \prod_{j= 1}^n \frac {(x-x_j)} {(1-x_j)} +(-1)^{\frac {n+1}{2}} \frac {P(-1)}{2} (x-1) \prod_{j= 1}^n \frac {(x-x_j)} {(1+x_j)}$$ Note that since $P(x)$ has degree $n$, hence the coefficient of $x^{n+1}$ is $0$. Equating the coefficient of $x^{n+1}$ in the above expression we get : $$0= P(x_i)\cdot \frac {(x^2-1)}{(x_i^2-1)} \prod_{j\neq i} \frac 1{(x_i-x_j)} + \frac {P(1)}{2} \prod_{j= 1}^n \frac 1{(1-x_j)} + (-1)^{\frac {n+1}{2}} \frac {P(-1)}{2} \prod_{j= 1}^n \frac 1{(1+x_j)}$$$$\implies 0=-F + \frac 12 + (-1)^{n+1} \frac 12$$ This completes the proof. $\blacksquare$

Great problem

There are two different interpolation polynomials for $n$ even and odd, whose values at $x_i$ are precisely$ \prod_{j \neq i} (1-x_{i} x_{j})$ these are: $$p_n(a)=\frac{(1-ax_1)(1-ax_2)...(1-ax_n)-(a-x_1)(a-x_2)...(a-x_n)}{1-a^2}$$for $n$ even. $$p_n(a)=\frac{(1-ax_1)(1-ax_2)...(1-ax_n)-a(a-x_1)(a-x_2)...(a-x_n)}{1-a^2}$$for $n$ odd. It easy to check that these are indeed polynomials, namely $1-a^2$ divides the numerators because they are zero at $a=1$ and $a=-1$. We also have from lagrange interpolation that $$p_n(a)=\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}(a-x_j)$$thus the expression the problem asks about is just the coefficient $c_{n-1}$ of the highest degree $a^{n-1}$ term in $p_n(a)$. -$p_n$ for $n$ even it is easy to see that is of degree $n-2$ thus $c_{n-1}=0$. -$p_n$ for $n$ odd you have a $-a^{n+1}$ highest degree term in the numerator and divided by $(1-a^2)$... you get $c_{n-1}=1$

First step (as in #5): Prove that the LHS is a polynomial in $x_i-x_j$. (Multiply with denominators and put $x_i=x_j$.) Second step (as in #5): Prove that the LHS is constant. (Fix $x_2,\dots,x_n$ and let $x_1 \to \infty$. The LHS remains bounded.) Third step (different from #5): Evaluate the LHS at a special point. Just choose the variables so that $x_1x_2=x_3x_4=\dots=1$. Now for even $n$, all the products become zero, hence the whole product vanishes. For odd $n$, all but one of the products become zero. Choosing $x_n=0$, the last product is seen to be $1$. Done.

An application of divided differences. It's enough to prove the claim in case non of the numbers $ x_i,i=1,2,\dots,n$ is equal to $ 1$ or $ -1$. Indeed, having proven this result and using the continuity of the expression, the general claim also follows. Denote $$ \displaystyle D(x_1,x_2,\dots,x_n):=\sum_{1 \leq i \leq n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}$$It easily follows $$ \displaystyle D(x_1,x_2,\dots,x_n,1,-1)=-D(x_1,x_2,\dots,x_n)+1+(-1)^{n-1}\quad (1)$$Set $ x_{n+1}:=1, x_{n+2}:=-1$ and consider the function $$ \displaystyle P(t):= \frac{\prod_{j=1}^{n+2}(1-tx_j)}{1-t^2}$$Note that $ P(t)$ is a polynomial of degree $ n$ since the denominator is canceled out with $(1-tx_{n+1})(1+tx_{n+2})$. We have $$ \displaystyle D(x_1,x_2,\dots,x_n,x_{n+1},x_{n+2})=\sum_{i=1}^{n+2}\frac{P(x_i)}{\prod_{j\ne i}(x_i-x_j)} +\frac{1}{2}+\frac{(-1)^{n-1}}{2}$$because the summands for $ i=1,2,\dots,n$ in the RHS are exactly the same as in the LHS and the last two terms are the needed corrections for the summands corresponding to $ i=n+1$ and $ i=n+2$. Note that $$ \displaystyle \sum_{i=1}^{n+2}\frac{P(x_i)}{\prod_{j\ne i}(x_i-x_j)}=0$$since it is a divided difference of the polynomial $ P(x)$ (of degree $ n$) taken at the points $ x_1,x_2,\dots,x_{n+2}$ (one may see some basic properties of divided differences in my blog). Hence $$ \displaystyle D(x_1,x_2,\dots,x_n,x_{n+1},x_{n+2})=\frac{1}{2}+\frac{(-1)^{n-1}}{2}$$Combining it with $ (1)$ we get $$ \displaystyle D(x_1,x_2,\dots,x_n)= \frac{1}{2}+\frac{(-1)^{n-1}}{2}$$and the result follows.

This is a proof without using Lagrange Interpolation.

Quite easy with Lagrange Interpolation. Consider some positive integer $1\le m\le n-1,$ and let $P(x)=x^m.$ Additionally, let $S_{k,i}$ denote the $k$th symmetric sum of $x_1,\dots,x_{i-1},x_{i+1},\dots,x_n.$ Since $P(x_i)=x_{i}^m$ for $1\le i\le n,$ we have the following by Lagrange interpolation:$$\sum_{1\le i\le n}\left(x_{i}^{m}\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\right)=x^m.$$Taking the coefficient of $x^{n-m-1}$ of both sides yields \[\sum_{1\le i\le n}\left((-1)^{m}x_{i}^{m}S_{m,i}\prod_{j\ne i}\frac{1}{x_i-x_j}\right)=\begin{cases} 0 & n\ne 2m+1\\ 1 & n=2m+1 \end{cases}\]Now note that \begin{align*} \sum_{1\le i\le n}\prod_{j\ne i}\frac{1-x_{i}x_{j}}{x_i-x_j} &= \sum_{1\le i\le n}\left(\left(\sum_{k=0}^{n-1}(-1)^{k} x_{i}^{k}S_{k,i}\right)\prod_{j\ne i}\frac{1}{x_i-x_j}\right)\\ &= \sum_{k=0}^{n-1}\left(\sum_{1\le i\le n}\left((-1)^{k}x_{i}^{k}S_{k,i}\prod_{j\ne i}\frac{1}{x_i-x_j}\right)\right). \end{align*}If $n$ is odd, there is exactly one value of $k$ for which $n=2k+1,$ and if $n$ is even, there are no such values. Thus, the expression above is equal to $1$ when $n$ is odd and $0$ when $n$ is even, as desired.

What a strange A5 this is. For those wondering why the Lagrange interpolation on two extra nodes is kinda forced: We start similarly to post $\#$6 to simplify writeup; until the part where we prove \[ g(x_1,x_2, \ldots, x_n) = \sum_{i=1}^{n}\left((1+x_i)^{n-1} \prod_{j\ne i}\dfrac{1-x_j}{x_i-x_j} \right) \]Now we let $1+x_i = y_i$. Note that $1- x_i = 2-y_i$ and $x_i-x_j = y_i-y_j$. So, \[ g(x_1,x_2, \ldots, x_n) = \sum_{i=1}^{n}\left(y_i^{n-1} \prod_{j\ne i}\dfrac{2-y_j}{y_i-y_j} \right) \]However, setting the polynomial of degree $n-1$ of which $P(y_i) = y_i^{n-1}$ implies that the $RHS$ is exactly $P(X)$ in interpolation form: \[ \sum_{i=1}^{n}\left(y_i^{n-1} \prod_{j\ne i}\dfrac{X-y_j}{y_i-y_j} \right)\]with $X = 2$. This implies that whatever sum the right is equal to $P(2)$, which is $2^{n-1}$. We are done.

The idea is that if we turn the given into a rational function of the form $\frac{P(x)}{Q(x)}$, then $P(x)$ has degree $\binom{n}{2} + (n - 1)$, and has a bajillion roots. Apply the substitution $x_i = \frac{y_i - 1}{y_i + 1}$. Notice that if $x_i = 1$ for some $i$, then any terms containing $x_i$ become $\frac{1 - x_ix_j}{x_i - x_j} = \frac{1 - x_j}{1 - x_j} = 1$, so we can just induct down and thus $x_i - 1$ is divisible by $P(x)$ or $P(x) - 1$. Henceforth assume none of them are $1$. This transforms the problem into evaluating \begin{align*} \sum_{1 \leq i \leq n} \prod_{j \neq i, 1 \leq j \leq n} \frac{y_i + y_j}{y_i - y_j}. \end{align*} Now, the key claim is that $\textbf{Claim: }$ $(y_i + y_j)$ divides $P(x)$ or $P(x) - 1$ depending on parity for all $i < j$, so $\binom{n}{2}$ total. WLOG focus on $y_1, y_2$. Then, notice that whenever $y_1 = -y_2$, the product with $y_1$ fixed and the product for $y_2$ identically becomes $0$. Then, considering any other occurences, we see that \begin{align*} \frac{y_k + y_1}{y_k - y_1} \cdot \frac{y_k + y_2}{y_k - y_2} = 1, \end{align*}and so by removing all these instances, we effectively remove two of the variables(preserving parity of $n$). Now induct down. $\square$ We can transform back, which tells us that the original crap is divisible by $x_i + x_j$ a bunch of times because our transformation is one to one. Since $P(x)$ or $P(x) - 1$ has $n + \binom{n}{2}$ roots, which is more roots than its degree, we know that it's identically $0$, thus done.

My solution was probably an interpolation in disguise. We proceed by induction on $n$, the induction base $n=2$ being obvious. If $x_{i}=\pm1$ for some $i$, we are done by induction hypothesis. Otherwise, take $x_n=x$ and view $\sum_{1\le i\le n}\prod_{i\ne j}\dfrac{1-x_ix_j}{x_i-x_j}$ as a rational function in $x$. Now, it is easy to see that, thanks to our induction hypothesis, this function is 0 if $n$ is even or 1 if $n$ is odd when $x=\pm1,\frac{1}{x_1},...,\frac{1}{x_{n-1}}$. (Note that, as at most one $x_i$ can be 0, at least $n$ of these numbers are well-defined). However, this is equivalent to the degree $n-1$ polynomials $(x-x_1)...(x-x_{n-1})\sum_{1\le i\le n}\prod_{i\ne j}\dfrac{1-x_ix_j}{x_i-x_j}$ and 0 or $(x-x_1)...(x-x_{n-1})\sum_{1\le i\le n}\prod_{i\ne j}\dfrac{1-x_ix_j}{x_i-x_j}$ and $(x-x_1)...(x-x_{n-1})$ coinciding in at least $n$ distinct points. Thus, they must be the same polynomial, and we are done. $\square$

Define $f_n(x_1,\ldots,x_n)$ and $P_n(x_1,\ldots,x_n)$ as follows: \[ f_n(x_1,\ldots,x_n) := \sum_{1 \le i \le n} \prod_{j \neq i} \frac{1-x_{i}x_{j}}{x_{i}-x_{j}} =: \frac{P_n(x_1,\ldots,x_n)}{\prod_{i<j}(x_i-x_j)}. \]In essence, $f_n$ is the function in the problem and $P_n$ is the polynomial obtained by multiplying through by the common denominator of $\prod_{i<j} (x_i-x_j)$. Claim 1: For all $1\le i \le n$, we have \[ x_i-1 \mid P_n(x_1,\ldots,x_n)- (n\mod 2)\prod_{i<j}(x_i-x_j).\]Proof: We will show $x_n-1 \mid P_n$, which suffices by symmetry. Let $g(x_1,\ldots,x_n) = f_n(x_1,\ldots,x_n)- (n\mod 2)$, then essentially the claim is saying that $x_i-1 \mid g_n(x_1,\ldots,x_n)$. Plugging $x_n=1$, we see \begin{align*} f(x_1,\ldots,x_{n-1},1) &= 1 + \sum_{1\le i\le n-1} \frac{1-x_i}{x_i-1}\prod_{\substack{j\not=i\\j\not=n}} \frac{1-x_ix_j}{x_i-x_j}\\ &=1-f_{n-1}(x_1,\ldots,x_{n-1}). \end{align*}By induction on the original problem statement, $f_{n-1}(x_1,\ldots,x_{n-1})=(n-1 \mod 2)$. Hence by the above, $f(x_1,\ldots,x_{n-1},1)=(n\mod 2)$, i.e. $g(x_1,\ldots,x_{n-1},1)=0$. Treating $g(x_1,\ldots,x_n)$ as a polynomial in $x_n$, this proves $x_n-1 \mid g(x_1,\ldots,x_n)$, as needed. $\blacksquare$ Claim 2: For all $1\le i<j \le n$, we have $x_i-x_j \mid P_n(x_1,\ldots,x_n)$. Proof: Fix $a<b$, and assume $x_a=x_b$. We will prove $P_n(x_1,\ldots,x_n)=0$. We have \[ f_n(x_1,\ldots,x_n) = \sum_{1\le i \le n} S_i(x_1,\ldots,x_n),\]where ``summand $i$'' $S_i$ is \[ S_i(x_1,\ldots,x_n)=\frac{(1-x_ix_1)\cdots (1-x_ix_{i-1})(1-x_ix_{i+1})\cdots (1-x_ix_n)}{(x_i-x_1)\cdots (x_i-x_{i-1})(x_i-x_{i+1})\cdots (x_i-x_n)}. \]For a fixed $k$, when we multiply $S_k$ through by $\prod_{i<j}(x_i-x_j)$, we get a product, and this product contains all terms of the form $(x_i-x_j)$, where $i\not = k$. In particular, $S_k$ for $k\not \in\{a,b\}$ is a product which contains $x_{a}-x_{b}$ (or its negative), and hence $S_k=0$ for $k\not \in \{a,b\}$. So actually $f_n = S_a+S_b$, so \[ P_n = S_a\prod_{i<j}(x_i-x_j) + S_b\prod_{i<j}(x_i-x_j)\]We see that \begin{align*} S_a\prod_{i<j}(x_i-x_j) &= \left(\prod_{i\not=a}1-x_ax_i \right) \cdot \left((-1)^{a-1} \prod_{i<j,i,j\not=a} (x_i-x_j)\right) \\ S_b\prod_{i<j}(x_i-x_j) &= \left(\prod_{i\not=b}1-x_bx_i \right) \cdot \left((-1)^{b-1} \prod_{i<j,i,j\not=b} (x_i-x_j)\right). \end{align*}where the $(-1)^{a-1}$ comes due to the fact that when we multiply $\prod (x_i-x_j)$, the terms $x_a-x_1,\ldots,x_a-x_{a-1}$ need to be switched in sign. We claim that on the RHS, the first terms are equal and the second terms are negatives. For the first terms, note that since $x_a=x_b$, \[ \prod_{i\not=a}(1-x_ax_i)=\frac{\prod_{i}(1-x_ax_i)}{1-x_a^2}=\frac{\prod_{i}(1-x_bx_i)}{1-x_b^2}=\prod_{i\not=b}(1-x_bx_i), \]as needed. For the second terms, we want to show \[ (-1)^{a-1} \prod_{i<j,i,j\not=a} (x_i-x_j) = - (-1)^{b-1} \prod_{i<j,i,j\not=b} (x_i-x_j). \]It suffices to show the ``complement''; however, we have to remove $x_a-x_b$ since it is equal to $0$. We want to show \[ (-1)^{a-1} \prod_{\substack{i<j\\ a\in \{i,j\}\\(i,j)\not=(a,b)}} (x_i-x_j) = -(-1)^{b-1} \prod_{\substack{i<j\\ b\in \{i,j\}\\(i,j)\not=(a,b)}} (x_i-x_j). \]Writing out the LHS and RHS above (omitting the $(-1)$ powers): \begin{align*} &(x_a-x_{a+1})\cdots (x_a-x_{b-1}) \underbrace{(x_a-x_{b+1})\cdots (x_a-x_n)}_{(\spadesuit)} \underbrace{(x_1-x_a)\cdots (x_{a-1}-x_a)}_{(\heartsuit)} \\ & \underbrace{(x_b-x_{b+1})\cdots (x_b-x_n)}_{(\spadesuit)} \underbrace{(x_1-x_b)\cdots (x_{a-1}-x_b)}_{(\heartsuit)} (x_{a+1}-x_b)\cdots (x_{b-1}-x_b). \end{align*}The corresponding sets of terms are underlined under common $(\heartsuit)$ and $(\spadesuit)$ braces. The remaining terms can be paired up in pairs that are negatives of each other. Since there are $b-a-1$ such pairs, the quotient of the LHS and RHS is $(-1)^{b-a-1}$. This proves the desired. $\blacksquare$ From Claim 2, we know \[ \prod_{i<j}(x_i-x_j) \mid P_n(x_1,\ldots,x_n). \]Hence $f_n(x_1,\ldots,x_n)$ is actually a polynomial, not just a rational function. Now, Claim 1 implies that \[ (x_1-1)\cdots (x_n-1) \mid f_n(x_1,\ldots,x_n) - (n\mod 2). \]But $\deg f_n(x_1,\ldots,x_n) = n-1$. Even with multiple variables, it is impossible for a degree $n$ polynomial to divide a nonzero degree $n-1$ polynomial. Therefore, $f_n(x_1,\ldots,x_n) = (n \mod 2)$.

Rewrite the expression as \begin{align*} \sum_{1\le i\le n} \prod_{j\ne i} \left(\frac{(x_i-1)(-1-x_j)}{x_i-x_j} + 1\right) &=n \quad + \sum_{\substack{S\subseteq \{1,\dots, n\} \\ |S| > 1}} \sum_{i\in S} \prod_{j\ne i \in S} \frac{(x_i-1)(-1-x_j)}{x_i-x_j} \\ &= n \quad + \sum_{\substack{S\subseteq \{1,\dots, n\} \\ |S| > 1}} \sum_{i\in S} (x_i-1)^{|S|-1}\prod_{j\ne i \in S}\frac{-1-x_j}{x_i-x_j} \end{align*}The key observation is the following: Claim: $\sum_{i\in S} (x_i-1)^{|S|-1}\prod_{j\ne i \in S}\frac{-1-x_j}{x_i-x_j} = (-2)^{|S|-1}.$ Proof. This follows straight from Lagrange Interpolation, where since for all $i\in S,$ $y_i = (x_i-1)^{|S|-1}$ it implies the unique polynomial is precisely $P(X) = (X-1)^{|S|-1}$ as $\deg P = |S|-1$ and there are $|S|$ such $x_i.$ In particular, in the above expression $X=-1,$ so the sum is equivalent to $P(-1) = (-2)^{|S|-1}.$ $\blacksquare$ In other words, the desired expression is equivalent to \begin{align*} n \quad + \sum_{\substack{S\subseteq \{x_1,\dots, x_n\} \\ |S| > 1}} (-2)^{|S|-1} &= n + \sum_{i=2}^n \binom{n}{i} (-2)^{i-1} \\ &= n + \frac{-(-1)^n + 1 - 2n}{2} \\ &= \frac{1-(-1)^n}{2}, \end{align*}For which the problem is proven.

We are trying to find the $[x^{n-1}]P(x)$ where $P(x_j)=\prod\limits_{k\ne j} (1-x_jx_k)$. Let $Q(x)=(1-x^2)P(x)$ and $C(x)=\prod\limits_{j=1}^n (x-x_j)$. Then $Q(\pm 1)=0, Q(x_j)=\prod\limits_{j=1}^n (1-x_jx_k)=x_j^n C(x_j^{-1})$. Since $\deg Q\le n+1$, it follows that $Q(x)=x^nC(x^{-1}) + (dx+t)\prod\limits_{j=1}^n (x-x_j) = x^nC(x^{-1})+(dx+t)C(x)$ Assume $x_j\ne 0,\pm 1$; if this is a polynomial identity proving this suffices. Thus, $C(1), C(-1)\ne 0$ and we have $d+t+1=0$ by plugging $x=1$, $-d+t+(-1)^n=0$ by plugging $x=-1$. This implies $d=\frac{(-1)^n-1}{2}$. Since $d=-[x^{n-1}]P(x)$, the conclusion follows.

Solved with rama1728. We solve with induction on $n$ with base case trivial. Now for any $n > 2,$ define the multivariable rational function $$\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}} = A_n(x_1, \dots x_n)$$and the multivariable polynomial $$B_n(x_1, \dots x_n) = \prod_{i<j}(x_i-x_j)(A_n - (\text{n's remainder mod 2})).$$This polynomial has at most degree $\binom{n}{2} + (n-1).$ But for every $x_i,$ we know $x_i - 1$ and $x_i+1$ divide $B_n$ by the inductive hypothesis, as well as all the terms of the form $x_i-x_j.$ That yields $\binom{n}{2} + 2n$ terms dividing $B_n,$ more than its degree. So $B_n$ is a zero polynomial as desired. $\blacksquare$

Sketch: consider multiplying the given expression minus $n\pmod{2}$ by the vandermonde determinant. The resulting expression is a polynomial with degree $\frac{n(n+1)}{2}-1$. However, it vanishes whenever $x_i=x_j$ (direct expansion) and $x_i=1$ (induct downwards), which consist of $\frac{n(n+1)}{2}$ inputs, hence it's identically zero.

Clear denominators by multiplying by $$\prod_{i<j} (x_i-x_j),$$so we want to prove that $$\sum_{1 \leq k \leq n} (-1)^{i-1} \prod_{i \neq k} (1-x_ix_k) \prod_{i<j,k \neq i,j} (x_i-x_j)-(n\%2)\prod_{i<j} (x_i-x_j)=0.$$Viewing this as a polynomial identity in $x_1,\ldots,x_n$, this evidently has degree $\binom{n-1}{2}+2(n-1)=\frac{n^2+n}{2}-1$ if it's nonzero. The key idea of the problem is to then find a bunch of factors of the LHS. Claim 1: $x_i-x_j$ divides the LHS for any $i<j$. Proof: Note that if $x_a=x_b=K$, then the LHS reduces to $$(-1)^{a-1}\prod_{i \neq a} (1-x_ix_a)\prod_{i<j,a \neq i,j} (x_i-x_j)+(-1)^{b-1}\prod_{i \neq b} (1-x_ix_b)\prod_{i<j,a \neq i,j} (x_i-x_j).$$It's easy to see that $\prod_{i \neq a} (1-x_ix_a)=(1-K^2)\prod_{i \neq a,b} (1-x_iK)=\prod_{i \neq b} (1-x_ix_b)$, so it suffices to prove that $$(-1)^{a-1}\prod_{i<j,b \in \{i,j\}} (x_i-x_j)+(-1)^{b-1}\prod_{i<j,a \in \{i,j\}} (x_i-x_j)=0,$$which is obvious (just write it out). $\blacksquare$ Claim 2: $x_a-1$ divides the LHS for any $a$. Proof: We work with the original expression and induct down with the base case of $n=2$ being trivial. If $F(n)$ denotes the expression for $n$ variables, then $$F(n)=1-F(n-1),$$from which we easily get $F(n)=n\%2$ for all $n$, hence our polynomial indeed vanishes whenever $x_a=1$. $\blacksquare$ It follows that the polynomial LHS is divisible by $$\prod_{i<j} (x_i-x_j) \prod_{1 \leq i \leq n} (x_i-1),$$which clearly has degree $\binom{n}{2}+n=\frac{n^2+n}{2}$. But this is greater than the degree of the RHS, so the RHS must equal zero, implying the desired result. $\blacksquare$

Let \[P(a_1, a_2, \dots, a_n) = \prod_{1 \le i < j \le n} (a_j - a_i).\]By the Vandermonde determinant, the following is true: \[P(a_1, a_2, \dots, a_n) = \sum_{\pi\text{ permutation of }0, 1, \dots, n-1}\text{sign}(\pi)\prod_{i=0}^{n-1}a_{i+1}^{\pi(i)}.\]The LHS of the given equation can be rewritten as \[\sum_{i=1}^n \left(\prod_{j=1}^{i-1} \frac{1 - x_ix_j}{x_i - x_j}\right)\left(\prod_{j=i+1}^n \frac{x_ix_j - 1}{x_j - x_i}\right).\]By introducing a factor of $P(x_1, x_2, \dots, x_n)$ to cancel the $x_i-x_j$ and $x_j - x_i$'s in the denominators, we can rewrite this as \[\frac{1}{P(x_1, x_2, \dots, x_n)}\sum_{i=1}^n \left(\prod_{j=1}^{i-1} 1 - x_ix_j\right)\left(\prod_{j=i+1}^n x_ix_j - 1\right)\left(\prod_{1 \le j < k \le n, j \neq i, k \neq i}x_k - x_j\right),\]which can be written as \[\frac{1}{P(x_1, x_2, \dots, x_n)}\sum_{i=1}^n x_i^{n-1}\left(\prod_{j=1}^{i-1} \frac{1}{x_i} - x_j\right)\left(\prod_{j=i+1}^n x_j - \frac{1}{x_i}\right)\left(\prod_{1 \le j < k \le n, j \neq i, k \neq i}x_k - x_j\right),\]which simplifies greatly to \[\frac{1}{P(x_1, x_2, \dots, x_n)}\sum_{i=1}^n x_i^{n-1}P\left(x_1, x_2, \dots, x_{i-1}, \frac{1}{x_i}, x_{i+1}, \dots, x_n\right).\]Substituting the Vandermonde determinant expression for $P$ gives \[\frac{1}{P(x_1, x_2, \dots, x_n)}\sum_{i=1}^n x_i^{n-1}\sum_{\pi\text{ permutation of }0, 1, \dots, n-1}\text{sign}(\pi)x_i^{-\pi(i-1)}\prod_{j=0, j+1\neq i}^{n-1}x_{j+1}^{\pi(j)},\]or \[\frac{1}{P(x_1, x_2, \dots, x_n)}\sum_{i=1}^n \sum_{\pi\text{ permutation of }0, 1, \dots, n-1}\text{sign}(\pi)x_i^{n - 1 -\pi(i-1)}\prod_{j=0, j+1\neq i}^{n-1}x_{j+1}^{\pi(j)}.\]This expression, excluding the $\frac{1}{P(x_1, x_2, \dots, x_n)}$ factor, is a polynomial in $x_1, x_2, \dots, x_n$; call it $Q(x_1, x_2, \dots, x_n)$. Let's look at the coefficient of a specific monomial, $x_1^{e_1}x_2^{e_2}\dots x_n^{e_n}$, in $Q$. As shown by the above expression which gives $Q$ as a sum of monomials, in order for the coefficient to be nonzero, it must be possible to generate the sequence $(e_1, e_2, \dots, e_n)$ by by starting from a permutation and replacing one of its elements, $e_k$, with $n - 1 - e_k$. Case 1: $n$ is even. Then $e_k \neq n - 1 - e_k$, so the changed element of the permutation must actually become something else, i.e. equal to another element of the permutation. The resulting sequence $e$ of exponents will have a single pair of duplicate elements. As a result, this sequence can be generated by starting from two different permutations $\pi_1$ and $\pi_2$, each corresponding to one of the duplicated elements being changed. Moreover, $\pi_1$ and $\pi_2$ differ by a single transposition (at the location of the duplicated pair), so they have opposite parity. The contributions to the coefficient of $Q$ from the two permutations thus cancel each other out due to the $\text{sign}(\pi)$ factor. Therefore the coefficient is zero, so $Q$ is zero and correspondingly the original expression is zero, as desired. Case 2: $n$ is odd. When the changed element of the permutation becomes equal to a different element of it (creating a duplicate pair in the sequence $e$), the same argument from case $1$ applies to show that the coefficient is zero. However, when $n$ is odd, the element of $\pi$ satisfying $\pi(k) = \frac{n-1}{2}$ does not change when it is supposed to be "changed" by being selected as $i$. As a result, every permutation $\pi$ produces a single term in $Q$ equal to $\text{sign}(\pi)\prod_{i=0}^{n-1}x_{i+1}^{\pi(i)}$. The sum of these over all $\pi$ is precisely $Q = P(x_1, x_2, \dots, x_n)$, cancelling with the factor of $\frac{1}{P(x_1, x_2, \dots, x_n)}$ to give a final answer of 1.

A somewhat convoluted Lagrange solution: Rewrite as $\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \left(-x_j + (1+x_j)\frac{1-x_j}{x_i-x_j} \right)$, and binomial expand it. Given a subset $S$ with $|S| \ge 2$ of $[n]$, define $$A_S = \sum_{i \in S} \prod_{j \in S, j\neq i}\left(\left(1+x_j \right)\frac{1-x_j}{x_i-x_j} \right) .$$This is equivalent to $P(1)$ if $P(X) = \sum_{i \in S} \prod_{j \in S, j\neq i}\left(\left(1+x_j \right)\frac{X-x_j}{x_i-x_j} \right)$. $P$ is a degree $|S|-1$ polynomial, satisfying $(1+x)P(x) = \prod_{i \in S} (1+x_i)$ for all $x \in S$. Thus, $(1+X)P(X) = c\prod_{i \in S} (X-x_i) + \prod_{i \in S} (1+x_i)$, for some constant $c$, which is also the leading coefficient of $P$. Given the first form of $P$, the leading coefficient is $c=\sum_{i \in S} \prod_{j \in S, j\neq i}\left(\frac{1+x_j }{x_i-x_j} \right)$, which by Lagrange Interpolation is equal to $(-1)^{|S|-1}$. In all, this gives $(1+X)P(X) = -\prod_{i \in S} (x_i-X) + \prod_{i \in S} (1+x_i) \implies A_S = P(1)= \frac{-\prod_{i \in S} (x_i-1) + \prod_{i \in S} (x_i+1)}{2}$. Now, note that \begin{align*} \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \left(-x_j + (1+x_j)\frac{1-x_j}{x_i-x_j} \right) &= \sum_{S \in [n], |S| \ge 2} \left(A_S \prod_{i \notin S} (-x_i)\right) + \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} (-x_j) \\ &= \frac{\sum_{S \in [n], |S| \ge 2} \left(\left(-\prod_{i \in S} (x_i-1) + \prod_{i \in S} (x_i+1) \right) \prod_{i \notin S} (-x_i)\right)}{2} + \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} (-x_j) \\ &= \frac{\left[ -\prod_{i=1}^n [(x_i-1) - (x_i)] - (n-1) \prod_{i=1}^n x_i - \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} (-x_j) \right]}{2} \\ &+ \frac{ \left[ \prod_{i=1}^n [(1+x_i) - (x_i)] + (n-1) \prod_{i=1}^n x_i - \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} (-x_j) \right]}{2} + \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} (-x_j) \\ &= \frac{-(-1)^n + (1)^n}{2}. \end{align*} This proves the desired result.

Set $LHS=A.$ For even $n$ we consider polynomial $$P(x)=\prod_{i=1}^n (1-xx_i)-\prod_{j=1}^n (x-x_j)$$which has roots $x=\pm 1,$ and so function $f(x)=\frac{P(x)}{1-x^2}$ is a polynomial. Using Lagrange interpolation we get $$f(x)=\sum_{i=1}^n P(x_i)\prod_{j\neq i} \frac{x-x_j}{x_i-x_j}=\sum_{i=1}^n \prod_{j\neq i} (x-x_j) \frac{1-x_ix_j}{x_i-x_j},$$whose coefficient of $x^{n-1}$ is thus $A$ and equals to $0$ since $\deg f\leq \deg P-2\leq n-2.$ For odd $n$ we consider polynomial $$Q(x)=\prod_{i=1}^n (1-xx_i)-x\prod_{j=1}^n (x-x_j).$$In the same way we show that $g(x)=\frac{Q(x)}{1-x^2}$ is a polynomial whose coefficient of $x^{n-1}$ is $A$ and equals to $1.$

Solved with anurag27826 Claim: $x_i-x_j$ divides $kS$, where $S$ is the given expression and $k$ is the product of $x_i-x_j$ over $i \neq j$ Proof. It suffices to show that $x_1-x_2$ divides $kS$. Note that whenever $i$ is neither $1$ nor $2$, then these terms get cancelled when $x_1=x_2$. So when $i=1$ or $i=2$, then factoring $\frac{1-x_1 x_2}{x_1-x_2}$ out, and then putting $x_1 = x_2$, everything cancels, and we get $0$, so this finishes our claim. Now coming to proving the main part of the problem, by the above argument, $S$ is itself a Polynomial in $(x_1, \dots, x_n)$ so if we fix all $x$ except for $x_1$, then We have a Polynomial of degree 0 in $x_1$, so it must be constant. Putting $x_1 = 1$, we are done by induction, since the base case $n = 2$ is trivial.

Let $Q(x) = \sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{x-x_{i} x_{j}}{x_{i}-x_{j}}$. I claim $Q(x) = 0$ for even $n$ and $Q(x) = x^{\frac{n-1}{2}}$ for odd $n$. For $n = 1,2$ this is trivial. Now we'll prove this by induction. It suffices to prove that they coincide for $n$ values of $x$. I claim $x = x_ax_b$ works. It's not too hard to see that this suffices for $n\ge 3$. So let's compute: \[Q(x_ax_b) =\sum_{i \leqslant n, i\ne a,b} \prod_{j \neq i} \frac{x_ax_b-x_{i} x_{j}}{x_{i}-x_{j}} =\sum_{i \leqslant n, i\ne a,b} \frac{(x_ax_b - x_ix_a)(x_ax_b - x_ix_b)}{(x_i - x_b)(x_i - x_a)}\prod_{j \neq i,a,b} \frac{x_ax_b-x_{i} x_{j}}{x_{i}-x_{j}}\]\[ = x_ax_b\sum_{i \leqslant n, i\ne a,b}\prod_{j \neq i,a,b} \frac{x_ax_b-x_{i} x_{j}}{x_{i}-x_{j}} = x_ax_b \left\{\begin{array}{ll} 0, & \text { if } n \text { is even; } \\ (x_ax_b)^{\frac{n-3}{2}}, & \text { if } n \text { is odd. } \end{array}\right. \]by the induction hypothesis. This concludes the proof.

Let $P(x_1, \dots, x_n)$ be the given expression, and let $F(x_1, \dots, x_n)$ be \[\prod_{1\le j < k\le n} x_j - x_k.\]Then, we get \[(P\cdot F)(x_1,\dots,x_n) = Q(x_1,\dots,x_n) = \sum_{i=1}^n (-1)^{i-1} \prod_{\substack{1\le j < k\le n \\ j, k \ne i}}(x_j - x_k) \prod_{\substack{1\le j\le n \\ j\ne i}} (1 - x_ix_j),\]which is a polynomial in our $n$ variables. Claim: $Q$ is divisible by $F$. Proof. It suffices to show that $x_i - x_j$ always divides $Q$. WLOG take $(i, j) = (1, 2)$. Plug in $x_1 = x_2 = t$. Then, in the summation for $Q$, all terms with $i\ne 1, 2$ vanish, leaving us with two products which can be easily verified to be negatives of one another, hence $Q(t, t, x_3, \dots, x_n) = 0$ as desired. $\blacksquare$ Now, fix $x_2$ through $x_n$ and let $x_1$ be variable, giving polynomials \[q(x) = Q(x, x_2, \dots, x_n),\quad f(x) = F(x, x_2, \dots, x_n).\]Then, one can easily observe that $\deg q = \deg f = n - 1$; this says that $q = \lambda f$ for some scalar $\lambda$ because $f \mid q$. But then, this means $P\equiv \lambda$ --- that is, $P$ is constant! It therefore suffices to show $n$-tuples for $n$ odd and $n$ even which yield the claimed values. If $n = 2k$, then taking $x_i = i + 1$ for $1\le i\le k$ and $x_i = \frac{1}{i+1 - k}$ for $k + 1\le i \le 2k$ means that, in every single term, there is a factor of $1 - x_ix_{i+k} = 1 - 1 = 0$, hence the sum is 0. If $n = 2k + 1$, then just add $x_{2k+1} = 1$. Everything but the last term dies, and then the final term is \[\prod_{1\le j\le 2k} \frac{1 - x_j}{1 - x_j} = 1.\]

We present two solutions. The key in both solutions is how the expression plays out nicely for $x_i = 1$. First Solution (Lagrange Interpolation): The key is that by Lagrange Interpolation, we have $$[x^{n-1}]P(x) = \sum_{i=1}^n P(x_i) \cdot \prod_{j \neq i}\frac 1{x_i-x_j}.$$To solve the problem, we use the $P(x_i)$ value judiciously. Define a polynomial $$P(x) = \prod_{i=1}^n (1-xx_i).$$Then notice $$P(x_i) = (1-x_i^2)\prod_{j \neq i}(1-x_ix_j).$$To deal with the extra term, we instead use Lagrange interpolation on the points $x_1, x_2, \dots, x_n, -1, 1$, to get $$[x^{n+1}]P(x) = \sum_{i=1}^n \left(\frac{\prod_{j=1}^n (1-x_ix_j)}{(x_i^2-1)\prod_{j \neq i} (x_i-x_j)}\right) + \frac{\prod_{i=1}^n (1-x_i)}{2\prod_{i=1}^n (1-x_i)} + \frac{ \prod_{i=1}^n (1+x_i)}{(-2) \prod_{i=1}^n (-1-x_i)}.$$Equivalently, as $\deg P = n$, $$0 = \sum_{i=1}^n \left(\prod_{j=1}^n \frac{1-x_ix_j}{x_i-x_j}\right) + \frac{1-(-1)^n}2.$$From this the result immediately follows. $\blacksquare$ Second Solution (Roots): Define the polynomial $$P(x_1, x_2, \dots, x_n) = \prod_{i < j} (x_i - x_j) \left(\sum_{i=1}^n \prod_{j \neq i} \frac{1-x_ix_j}{x_i-x_j} - \frac{1-(-1)^n}2\right).$$We wish to show that $P$ is identically zero. To do so, I claim $P$ vanishes when $x_i = x_j$ and when $x_i = 1$. For the first part, it suffices to show that the $k$ and $\ell$ terms in the sum sum to zero when $a = x_k = x_\ell$, as all other terms disappear automatically. To do so, it suffices to show that $$\frac{\prod_{j \neq k} (1-ax_j)}{\prod_{j \neq k, \ell} (a-x_j)} = \frac{\prod_{j \neq \ell}(1-ax_j)}{\prod_{j \neq k, \ell} (a-x_j)}.$$(The equality is negated as we cancel two terms $x_k - x_\ell$ and $x_\ell - x_k$ that are negatives of each other.) However, this is evident. For the second part, if $x_i = 1$, one of the terms completely vanishes, and we can actually argue inductively: the expression $P(n)$ for $n$ variables satisfies $$P(n) = 1-P(n-1)$$assuming that $P(n-1)$ is constant. Hence the polynomial vanishes in this case too. Now the LHS is divisible by a polynomial with degree ${n \choose 2} + n > {n+1 \choose 2} - 1$, which is implies it is identically zero.

this is my first A5 no way (probably my hardest alg solve?) We go by induction, with two base cases: $n=2$ is trivial, so we'll just do $n=3$ out right here. \[ \frac{(1 - ab)(1 - ac)}{(a - b)(a - c)} + \frac{(1 - ba)(1 - bc)}{(b - a)(b - c)} + \frac{(1 - ca)(1 - cb)}{(c - a)(c - b)}. \]We multiply out by $(a-b)(b-c)(c-a)$. Namely we obtain \[ -(1 - ab)(1 - ca)(b - c) - (1 - ab)(1 - bc)(c - a) - (1 - ca)(1 - bc)(a - b). \]This is just \[ \providecommand{\sumcyc}{\sum_{\text{cyc}}} -\sumcyc (1 - ab)(1 - ca)(b - c) = -\sumcyc a^2b^2c - a^2bc^2 - ab^2 + ac^2 + b - c = -\sumcyc ac^2 - ab^2 = (a-b)(b-c)(c-a). \]Thus our original thing must have been $1$. We shall begin our induction. Let $n + 2$ be even and suppose it works for $n$. Then, the multivariable rational function \[ \prod_{1 \le i < j \le n} (x_i - x_j) \left( \sum_{1 \le i \le n} \prod_{\substack{j \neq i \\ 1 \le j \le n}} \frac{1 - x_i x_j}{x_i - x_j} \right) \]is in fact a multivariable polynomial. Now consider the case where $x_a - x_b = 0$ for distinct $a$, $b$. This vanishes almost all the terms except for the $i=a$ and $i=b$ terms on the inside sum. So it is sufficient to consider those terms without the $x_a - x_b$ or $x_b - x_a$ on the denominator. We'll multiply by $x_a - x_b$ so the $i=b$ term has a negative sign. Now note that the numerators and denominators are identical as $x_a = x_b$, so we are subtracting something by itself and getting $0$. Thus $x_a - x_b$ is a factor for all distinct $a$, $b$. $\textbf{Here's the big one}$: I claim that $x_a x_b - 1 = 0$ for distinct $a$, $b$ in the range is a factor. Suppose they have distinct value; if they're equal we have handled that already. Then exactly two terms vanish. Now for $j \neq a$, $j \neq b$, consider the factors \[ \frac{(1 - x_j x_a)(1 - x_j x_b)}{(x_j - x_a)(x_j - x_b)}. \]Multiplying the numerator and denominator by $x_a$, one can observe that we have \[ \frac{(1 - x_jx_a)(x_a - x_j x_ax_b)}{(x_j - x_a)(x_ax_j - x_a x_b)} = \frac{(1 - x_j x_a)(x_a - x_j)}{(x_j - x_a)(x_j x_a - 1)} = 1 \]and can be from the term. This returns the sum the $n$ variable case! But we assumed by induction that this must be $0$, so we have a lot more factors. In particular, $\prod_{1 \le i < j \le n} (x_i - x_j)(x_ix_j - 1)$ must be a factor. From here note that the first half of the product is nonzero, and by choosing all $x_ix_j$ from the second half of the product, we can obtain many nonzero degree $3\binom{n}{2}$ terms. This is bad as the highest degree of the other multivariable polynomial is $\binom{n}{2} + n - 1 < 3\binom{n}{2}$. So we must have that the multivariable polynomial is in fact $0$. \endproof Let $n + 2$ be odd and suppose it holds that for $n$ that the function is $1$. Then consider \[ \prod_{1 \le i < j \le n} (x_i - x_j) \left( \sum_{1 \le i \le n} \prod_{\substack{j \neq i \\ 1 \le j \le n}} \frac{1 - x_i x_j}{x_i - x_j} - 1 \right). \]By exactly the same arguments as above, we have the same polynomial dividing the multivariable polynomial which again by counting degrees leaves it to be zero, whence the inside sum is $1$. This completes the induction.

We prove this for all $x_j \ne \pm 1$ that are distinct, which due to being a polynomial identity gives the result for all distinct $x_j \ne x_k$. (Sketch: Expand then Combo Null). Define $P(x) = x \cdot \prod_{j=1}^n (x_j x - 1)$ and $Q(x) = \prod_{j=1}^n (x - c_j) \cdot (x^2 - 1)$. It then follows that \[ s(x_j) = \lim_{x \to x_j} \frac{P(x) \cdot (x - x_j)}{Q(x)} = x_j \cdot \prod_{1 \le j \ne k \le n} \frac{x_jx_k - 1}{x_j - x_k} \]Then, by partial fraction decomposition theory it follows that \[ \sum_{j=1}^n \frac{s(x_j)}{-x_j} + \frac{s(1)}{-1} + \frac{s(-1)}{1} = \frac{P(0)}{Q(0)} = 0 \]so $\frac{s(1)}{-1} + \frac{s(-1)}{1}$ is the desired result. We have that \[ s(1) = \frac{1 \cdot \prod_{j=1}^n (x_j - 1)}{\prod_{j=1}^n (1 - x_j) \cdot 2} = \frac{1}{2} \cdot (-1)^n \]and similarily $s(-1) = 1^n$, so the result simplifies as $\frac{1}{2} \cdot (1^{n-1} + (-1)^{n-1})$ as desired, which is invariant under multiplication by $(-1)^{n-1}$.

We use induction to prove this problem. $n=1,2$ is trivial. Now consider ${n}.$ Define $\coth x=\frac{e^x+e^{-x}}{e^x-e^{-x}}=\frac{e^{2x}+1}{e^{2x}-1}.$ Then we notice that $\coth (\alpha -\beta )=\frac{1-\coth\alpha\coth\beta}{\coth\alpha -\coth\beta}.$ For $\forall 1\le i\le n,$ let $x_i=\coth\theta_i.$ Let $f(n)=\sum\limits_{i=1}^n \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}},$ then $$\begin{aligned}f(n) &=\sum\limits_{i=1}^n \prod_{j \neq i}\coth (\theta_i -\theta _j)\\ &=\coth (\theta_1-\theta_2)\left(\prod\limits_{i=3}^n \coth (\theta_1-\theta_i)-\prod\limits_{i=3}^n \coth (\theta_2-\theta_i)\right)\\ &+\sum\limits_{i=3}^n\coth (\theta_i-\theta_1)\coth (\theta_i-\theta_2)\prod_{\substack{j\neq i\\j\ge 3}}\coth (\theta_i-\theta_j). \end{aligned}$$Let $P=\sum\limits_{i=3}^n\coth (\theta_i-\theta_1)\coth (\theta_i-\theta_2)\prod_{\substack{j\neq i\\j\ge 3}}\coth (\theta_i-\theta_j).$ Then by $$\coth (\theta_i-\theta_1)\coth (\theta_i-\theta_2)=1+\coth (\theta_1-\theta_2)\left(\coth (\theta_i-\theta_1)-\coth (\theta_i-\theta_2)\right),$$we have $$\begin{aligned}P &=f(n-2)+f(n-2)\sum\limits_{i=3}^n\coth (\theta_1-\theta_2)\left(\coth (\theta_i-\theta_1)-\coth (\theta_i-\theta_2)\right)\\ &=f(n-2)+\coth (\theta_1-\theta_2)\sum\limits_{i=3}^n\left(\coth (\theta_i-\theta_1)-\coth (\theta_i-\theta_2)\right)\sum\limits_{i=3}^n\prod_{\substack{j\neq i\\j\ge 3}}\coth (\theta_i -\theta _j).\end{aligned}$$Therefore $f(n)=f(n-2)$ is equivalent to $$\prod\limits_{i=3}^n \coth (\theta_1-\theta_i)-\prod\limits_{i=3}^n \coth (\theta_2-\theta_i)+\sum\limits_{i=3}^n\left(\coth (\theta_i-\theta_1)-\coth (\theta_i-\theta_2)\right)\sum\limits_{i=3}^n\prod_{\substack{j\neq i\\j\ge 3}}\coth (\theta_i -\theta _j)=0.$$$$\begin{aligned}{}{}{}{}&\Leftrightarrow\prod\limits_{i=3}^n \coth (\theta_1-\theta_i)+\sum\limits_{i=3}^n\coth (\theta_i-\theta_1)\sum\limits_{i=3}^n\prod_{\substack{j\neq i\\j\ge 3}}\coth (\theta_i -\theta _j)\\&=\prod\limits_{i=3}^n \coth (\theta_2-\theta_i)+\sum\limits_{i=3}^n\coth (\theta_i-\theta_2)\sum\limits_{i=3}^n\prod_{\substack{j\neq i\\j\ge 3}}\coth (\theta_i -\theta _j).\end{aligned}$$Which is trivial because $f(n-1)$ is a constant.$\blacksquare$

reposted from blog Let $S$ be the sum. Assume that $x_i\not\in \{-1,0,1\}$. Those cases are easy by continuity. If Lagrange Interpolation is going to work, we need to find suitable \[a,P(x_1),P(x_2),\dots,P(x_n)\]such that \[P(a)=S=\sum_{i=1}^n P(x_i)\prod_{j\ne i} \frac{a-x_j}{x_i-x_j}.\]After figuring out that $a=0$ works pretty well, we are led to \[P(x_i):=\prod_{j\ne i} \left(x_i-\frac{1}{x_j}\right).\]Now the whole point of using a polynomial is because now our expression is almost symmetric. In light of this, write \[(x_i^2-1)P(x_i)=x_i\prod_{j=1}^n \left(x_i-\frac{1}{x_j}\right).\]Let $A(x)=(x^2-1)P(x)$. Let \[B(x)=x\prod_{j=1}^n \left(x-\frac{1}{x_j}\right).\]Everything after this is straightforward. Note that $\text{deg }A=\text{deg }B=n+1$ and the two polynomials are the same at $x_i$ for all $1\le i\le n$. Hence write \[A-B=C\prod_{j=1}^n (x-x_j)\]for some constant or linear polynomial $C$. Notice that $A(-1)=A(1)=0$, and notice also that $B(0)=0$. What does this mean? Well, since $\text{deg }C\le 1$, we have \[C(0)=\frac{1}{2}(C(-1)+C(1)).\]Since $P(0)$ follows from $C(0)$, we just need $C(-1)$ and $C(1)$. Here's what my calculations gave me: \[C(-1)=\frac{1}{x_1x_2\dots x_n}\]\[C(1)=(-1)^{n+1}\frac{1}{x_1x_2\dots x_n}\]\[C(0)=\frac{1}{2}\cdot \frac{1}{x_1x_2\dots x_n}\cdot (1+(-1)^{n+1})\]now we have \[S=P(0)=B(0)-A(0)=(-1)^{n+1}\cdot x_1x_2\dots x_n\cdot C(0)=\frac{1}{2}(1+(-1)^{n+1})\]hence for $n$ even we have $S=0$ and for $n$ odd we have $S=1$. Done!

y-is-the-best-_ wrote: Let $x_1, x_2, \dots, x_n$ be different real numbers. Prove that \[\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}=\left\{\begin{array}{ll} 0, & \text { if } n \text { is even; } \\ 1, & \text { if } n \text { is odd. } \end{array}\right.\] We claim that $$(x^2-1)\sum_{i=1}^n \prod_{j\neq i} \frac{1-x_i x_j}{x_i-x_j} (x-x_j)+\prod_{j=1}^n (1-x x_j) =\begin{cases} \prod_{j=1}^n (x-x_j) \qquad 2\mid n \\ x\prod_{j=1}^n (x-x_j) \qquad 2\nmid n\end{cases}$$holds true for all $x$. This is true because the degree is $n+1$ but the two sides agree at $n+2$ points, namely $x=-1,1,x_1,\dots,x_n$. Now comparing the coefficient of $x^{n+1}$ of both sides directly gives the result.

Somehow I didn't find the same solution as mine, although I, as almost everybody else, just write Lagrange Interpolation. Let $P(x)=\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{(1-x_{i} x_{j})(x-x_{j})}{x_{i}-x_{j}}$. Note that the desired sum is $x^{n-1}$ coefficient of $P$ Then $P(x_i)=\prod_{j \neq i} 1-x_ix_j=\frac{\prod 1-x_ix_j}{1-x_i^2}$ So all $x_i$ are roots of $(1-x^2)P(x)-\prod (1-xx_i)$. The degree of this polynomial $\leq n+1$, thus we know that $$(1-x^2)P(x)-\prod (1-xx_i)=(kx+b)\prod (x-x_i)$$Substitute $x=1$ and $x=-1$ to get: $-1=k+b$ and $(b-k)=(-1)^{n+1}$. From this we know that $k=\frac{-1-(-1)^{n+1}}{2}$. The desired sum is $-k$, so our answer is $\frac{1+(-1)^{n+1}}{2}$ Note that this solution actually works only if none of $x_i$ is $1$ or $-1$. But in this case just take the limit as $x_i \rightarrow 1 \ or -1$

We will prove the result for when $1\not\in\{x_1^2,x_2^2,\dots,x_n^2\}$, the rest will follow by continuity. Define $R(x)=(x-x_1)(x-x_2)\dots(x-x_n)$. Consider the polynomial with degree at most $n-1$, $P$, which sends \[x_i\rightarrow\prod_{j\ne i}(1-x_ix_j).\]Let $Q(x)=(1-x_1x)(1-x_2x)\dots(1-x_nx)$. Then note that \[P(x_i)=\frac{1}{1-x_i^2}Q(x_i)\Longrightarrow P(x_i)(1-x_i^2)=Q(x_i).\]Note that $P(x)(1-x^2)-Q(x)$ has degree at most $n+1$ and has the $x_i$ as roots, so \[P(x)(1-x^2)-Q(x)=a R(x)(x-b).\]Now plug in $x=1,-1$ to get \[-R(1)=aR(1)(1-b)\]\[-(-1)^n R(-1)=aR(-1)(-1-b).\]Note that $R(1),R(-1)\ne 0$, so we get \[-1=a(1-b)\]\[-(-1)^n=a(-1-b).\]Subtract these to get \[2a=-1+(-1)^n\Longrightarrow a=\begin{cases}0 & n\text{ even} \\ -1 & n\text{ odd}\end{cases}.\]Note that $a$ is negative of the $x^{n-1}$ coefficient of $P(x)$, so that coefficient will be \[\begin{cases}0 & n\text{ even} \\ 1 & n\text{ odd}\end{cases}.\]Now by the Lagrange Interpolation Formula, we have that \[P(x)=\sum_{i} \prod_{j \ne i}(1-x_ix_j)\prod_{j\ne i} \frac{(x-x_j)}{x_i-x_j}.\]Take the $x^{n-1}$ coefficient to win. $\blacksquare$

Clearly the result holds when we have $2$ variables. Now I will prove it for $n$ variables, suppose the result holds for $n-1$ variables. We can suppose that $1\notin {x_2^2, x_3^2, \dots, x_n^2}$ as if the result holds when this holds, when this doesn't hold it must still hold by continuity. Now let $x_1=x$. Clearly if we clear the denominators, we get an $n$-th degree polynomial in terms of $x$. Let that polynomial be $P(x)$. First I will prove the result when $n$ is even. Clearly from the induction $P(1)=0$ and $P(-1)=0$. Now consider $P(x_k)$ for $k\neq 1$. We get: \[\prod_{j=2}^{1-xx_j}+\sum_{i=2}^{n}\left(((1-xx_i)\cdot \prod_{j=2, j\neq i}^{n}(1-x_ix_j)\cdot \prod_{j=2, j\neq i}^{n}\frac{x-x_j}{x_i-x_j}\cdot \frac{x-x_i}{x_i-x}\right)\]Clearly for all the terms of the summation when $i\neq k$ they are $0$. This leaves us with: \[\prod_{j=2}^{1-xx_j}+\left(((1-xx_k)\cdot \prod_{j=2, j\neq k}^{n}(1-x_kx_j)\cdot \prod_{j=2, j\neq k}^{n}\frac{x-x_j}{x_k-x_j}\cdot \frac{x-x_k}{x_k-x}\right)\]\[=\prod_{j=2}^{1-xx_j}-\left(((1-xx_k)\cdot \prod_{j=2, j\neq k}^{n}(1-x_kx_j)\right)\]\[=0\]Thus when $n$ is even this result holds. When $n$ is odd, we get that when $x$ is $1$ or $-1$ in the original condition the value is $1$ from induction. Now consider $P(x_k)$, clearly as to make this polynomial work, we cleared the denominators thus we want to show that $P(x_k)=0$ for any $k\in\{2, 3, \dots, n\}$. Clearly however the calculation, above still holds, so we get that $P(x_k)=0$ for any $k\in\{2, 3, \dots, n\}$. Thus as $P(x)$ is an $n$th degree polynomial this suffices.