# Prove that $\sum_{1\leq i\leq n}\prod_{j\neq i} \frac{1-x_ix_j}{x_i-x_j} = 0$ if $n$ is even and $1$ otherwise

Let $$x_1,\cdots, x_n$$ be different real numbers. Prove that $$\sum_{1\leq i\leq n} \prod_{j\neq i} \frac{1-x_ix_j}{x_i-x_j} = \begin{cases} 0,&\text{if }n\text{ is even}\\ 1,&\text{if }n\text{ is odd}\end{cases}.$$

Let $$f(t) = \prod_{i=1}^n (1-x_i t)$$. Note that $$f(x_i) = (1-x_i^2)\prod_{j\neq i} (1-x_ix_j)$$.

First, I think one can ignore the case where $$\{x_1,\dots, x_n\}\cap \{-1,1\}\neq \emptyset$$, but I'm not sure how to justify this, which is the point of this question.

I think I should use a similar approach to below. For instance, if one assumes that $$x_i = 1$$ and $$x_j=-1$$ for some $$i,j$$, Lagrange interpolation gives the following expression: $$\sum_{1\leq k\leq n, k\neq i,j} f(x_k) \dfrac{(x-1)(x+1)}{(x_k - 1)(x_k + 1)} \prod_{a\neq j,i,k} \dfrac{x-x_a}{x_k - x_a} + f(1) \dfrac{x+1}{1+1}\prod_{1\leq k\leq n, k\neq j,i} \dfrac{x-x_k}{1-x_k} + f(-1)\dfrac{x-1}{-1-1}\prod_{1\leq k\leq n,k\neq i,j}\dfrac{x-x_k}{-1-x_k}$$.

The issue is that we need one more interpolation point to uniquely determine $$f$$ in this case; the above expression clearly does not have to equal $$f$$.

Now assuming that we can ignore the above case, one can use Lagrange interpolation to get the following expression for $$f$$: $$\sum_{i=1}^n f(x_i) \dfrac{(x-1)(x+1)}{(x_i - 1)(x_i + 1)} \prod_{j\neq i} \dfrac{x-x_j}{x_i - x_j} + f(1) \dfrac{x+1}{1+1}\prod_{1\leq i\leq n} \dfrac{x-x_i}{1-x_i} + f(-1)\dfrac{x-1}{-1-1}\prod_{1\leq i\leq n}\dfrac{x-x_i}{-1-x_i}$$. Setting the coefficient of $$x^{n+1}$$ on both sides equal to zero, we eventually get that if $$H(x_1,\cdots, x_n)$$ denotes the desired rational function, then $$H(x_1,\cdots, x_n) = \dfrac{1}2 (1 +(-1)^{n+1})$$. Also there may be other methods involving multivariate polynomials.

• I understand and agree with all of this, but what's your question exactly ? Given that you've answered your own question, what more are you looking for ? Sep 11, 2022 at 17:18
• @EwanDelanoy my key question is that I can't justify why we can ignore the initial case. Sep 11, 2022 at 17:24

My solution is the same, and the answer your question, the key is CONTINUITY. This is a common trick in algebra (and often in linear algebra) where you have to prove that a giant polynomial expression $$P(x_1,\cdots,x_n)=Q(x_1,\cdots,x_n)$$ (say in this case, multiply both sides by $$\prod\limits_{i\ne j} (x_i-x_j)$$ to get $$P,Q$$) holds and it holds almost everywhere except for at certain places, you can use the fact that it is continuous if I fix all variables except for one that changes. Therefore, you can finish after you are done with the case $$\{x_1,\cdots,x_n\} \cap \{-1,1\} =\emptyset$$

Another application of this continuity technique is proving that $$\det(AB-xI)=\det(BA-xI)$$ for all $$n\times n$$ matrices $$A,B$$. You can first assume $$A$$ is invertible, so $$\det(AB-xI)=\det(ABA-xA)/\det(A)=\det(BA-xI)$$ and then use continuity to deal with $$A$$ non-invertible case.

Here is an alternate approach which is also based upon Lagrange polynomials. We start by expanding the numerator and obtain \begin{align*} \color{blue}{\sum_{1\leq i\leq n}}\color{blue}{\prod_{j\ne i}\frac{1-x_ix_j}{x_i-x_j}} &=\sum_{1\leq i\leq n}\left(\prod_{s\ne i}\left(1-x_ix_s\right)\right)\left(\prod_{j\ne i}\frac{1}{x_i-x_j}\right)\\ &=\sum_{1\leq i\leq n}\left(\sum_{k=0}^{n-1}(-1)^kx_i^k\sum_{{S\subseteq [n]\setminus\{i\}}\atop{|S|=k}} \prod_{s\in S}x_s\right)\left(\prod_{j\ne i}\frac{1}{x_i-x_j}\right)\\ &=\sum_{k=0}^{n-1}\sum_{1\leq i\leq n}\left((-1)^kx_i^k\sum_{{S\subseteq [n]\setminus\{i\}}\atop{|S|=k}} \prod_{s\in S}x_s\right)\left(\prod_{j\ne i}\frac{1}{x_i-x_j}\right)\tag{1} \end{align*} In (1) we expand the inner product according to the number $$k, 0\leq k\leq n-1$$ of terms $$x_ix_s$$. We also use the notation $$[n]:=\{1,2,\ldots,n\}$$.

We now consider functions $$\color{blue}{f_q(x)=x^q, 1\leq q\leq n-1}$$ and the Lagrange polynomials $$L_q(x)$$ with $$L_q(x_i)=x_i^q$$. \begin{align*} \color{blue}{L_q(x)=\sum_{1\leq i\leq n}x_i^q\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}=x^q =f_q(x)} \end{align*} We calculate the coefficient of $$x^{n-1-q}$$ from $$L_q(x)$$ and get \begin{align*} \color{blue}{[x^{n-1-q}]}\color{blue}{L_q(x)} &=\sum_{1\leq i\leq n}x_i^q[x^{n-1-q}]\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\\ &=\sum_{1\leq i\leq n}\left(x_i^q[x^{n-1-q}]\prod_{j\ne i}(x-x_j)\right)\prod_{j\ne i}\frac{1}{x_i-x_j}\\ &=\sum_{1\leq i\leq n}\left((-1)^qx_i^q\sum_{{S\subseteq [n]\setminus\{i\}}\atop{|S|=q}}\prod_{s\in S}x_s\right) \prod_{j\ne i}\frac{1}{x_i-x_j}\tag{2.1}\\ \end{align*} On the other hand we have \begin{align*} \color{blue}{[x^{n-1-q}]L_q(x)}=[x^{n-1-q}]x^q \color{blue}{=\begin{cases}1&\quad n=2q+1\\ 0&\quad n\neq 2q+1 \end{cases}}\tag{2.2} \end{align*}

Conclusion: Comparison of the expression in parentheses of (1) and (2.1) we see the claim follows thanks to (2.2).

This can also be done with complex integration a la this answer: https://math.stackexchange.com/a/877605/154826 (which actually references an answer to a similar question that I asked years ago).

For this case, we would consider the function $$f(z) = \frac{1}{z^2 - 1}\prod_{j=1}^n \frac{1 - z x_j}{z - x_j},$$ for which we can estimate the contour intgral $$\oint_{|z| = R} |f(z)| |\mathrm{d} z| = O(R^{-1}) \rightarrow 0$$.

Moreover, we can compute residues. Assuming that each $$x_i \neq \pm 1$$, there are simple poles at each $$x_j$$, where the corresponding residue is $$\mathrm{Res}(f; x_i) = \frac{1}{x_i^2 - 1} \prod_{j\neq i}\frac{1 - x_i x_j}{x_i - x_j} (1 - x_i^2) = -\prod_{j\neq i}\frac{1 - x_i x_j}{x_i - x_j}.$$

We also have simple poles at $$\pm 1$$, where the residues are \begin{align*} \mathrm{Res}(f; 1) &= \frac{1}{2} \prod_{j=1}^n \frac{1 - x_j}{1 - x_j} = \frac{1}{2}, \\ \mathrm{Res}(f; -1) &= -\frac{1}{2}\prod_{j=1}^n \frac{1 + x_j}{-1 - x_j} = \frac{(-1)^{n+1}}{2}. \end{align*}

The residue theorem then yields that $$\begin{gather*} -\sum_{i=1}^n\prod_{j\neq i}\frac{1 - x_i x_j}{x_i - x_j} + \frac{1}{2} + \frac{(-1)^{n+1}}{2} = 0, \\ \sum_{i=1}^n\prod_{j\neq i}\frac{1 - x_i x_j}{x_i - x_j} = \frac{1}{2} - \frac{(-1)^n}{2}, \end{gather*}$$ which is $$0$$ when $$n$$ is even and $$1$$ when $$n$$ is odd.

Others have covered how to then extend to the case where at least one of the $$x_i$$ are $$\pm 1$$.