2019 IMO SL #A5

Problem: 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.\]

Solution 1 (induction): We induct on $n$, and the base case is 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. $\square$

Solution 2 (Lagrange Interpolation): Let $F$ be the value of the expression in the problem. We will work with the 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 (aka nodes) $x_1,x_2,\dots,x_n,1,-1$. We get $$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)}.$$ Now, because $P(x)$ has degree $n$, we know that the coefficient of $x^{n+1}$ is $0$. Equating the coefficient of $x^{n+1}$ in the above expression, we obtain $$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,$$and this completes the proof. $\square$


Popular posts from this blog

1995 IMO #2

Inequality problem I made