# A polynomial identity

Let $x_1<x_2<\dots<x_n$ be $n$ real numbers. I'm trying to prove the following polynomial identity (I found this identity in an undergrad book): $$P(Y):=1+Y+Y^2+\cdots+Y^{n-1}= \sum_{k=1}^n \prod_{\underset{j\neq k}{1\le j \le n}} \frac{Yx_k-x_j}{x_k-x_j}$$

Since it is very similar to the Lagrange basis, I started to write that $$P(Y)=\sum_{k=1}^n P(x_k)\prod_{\underset{j\neq k}{1\le j \le n}} \frac{Y-x_j}{x_k-x_j}$$ but apparently I didn't find a way to transform this expression into the first one. Since the roots of $P$ are the $n$-th roots of unity (except $1$), I've considered also to prove that the RHS of the first equality as the same roots (but due to the fact that $x_1<x_2<\dots<x_n$ are random numbers it didn't seem like a good idea).

Do you have any hint for me?

First, we should show that the right-hand side is independant of the values $x_1,\ldots,x_n$.

By reducing everything to the same denominator, the right-hand side is of the form $Q(Y,x_1,\ldots,x_n)/\prod_{i<j} (x_i-x_j)$, where $Q$ is of degree $n(n-1)/2$ in the $x_i$ (it has the same degree as the denominator). We want to show that $Q$ is actually of the form $R(Y)\prod (x_i-x_j)$. To do that we show that $Q$ is divisible by $(x_1-x_2)$.

By looking at the first two terms of the right-hand side, they were originally of the form $(Yx_1-x_2)f(x_1,Y,x_3,\ldots,x_n)/(x_1-x_2)$ and $(Yx_2-x_1) f(x_2,Y,x_3,\ldots,x_n)/(x_2-x_1)$ where $f$ is some rational fraction. After putting them on the denominator $\prod_{i<j} (x_i-x_j)$, the numerators become of the form $(Yx_1-x_2)g(x_1,x_2,Y,x_3,\ldots,x_n)$ and $-(Yx_2-x_1)g(x_2,x_1,Y,x_3,\ldots,x_n)$ where $g$ is some polynomial. When you evaluate this sum when $x_1 = x_2$ you obtain $0$, which shows that the whole thing is a multiple of $(x_1-x_2)$.

As for the remaining $n-2$ terms, $(x_1-x_2)$ is a factor introduced when putting them on the denominator $\prod_{i<j} (x_i-x_j)$, so their numerators are all multiples of $x_1-x_2$.

Hence $(x_1-x_2)$ divides $Q(Y,x_1,\ldots,x_n)$. By a symmetry argument, so does $(x_i-x_j)$ for any pair $i<j$. Since the degree of $Q$ in the $x_i$ is $n(n-1)/2$, it follows that $Q$ is of the form $R(Y)\prod (x_i-x_j)$, and the right-hand side simplifies to $R(Y)$ where $R$ is a degree $n-1$ polynomial.

Now, to identify $R$, we can choose whatever $x_i$ we want. In particular, take the complex numbers $x_i = \exp(2i\pi/n)$.

Now, using the well-known fact that $\prod_{i \neq n} (X-x_i) = 1+X+\ldots+X^{n-1}$, the right-hand side becomes :
$$\sum_k \prod_{j \neq k} \frac {Yx_k-x_j}{x_k-x_j} = \sum_k \prod_{j \neq k} \frac {Y-x_j/x_k}{1-x_j/x_k} = \sum_k \prod_{j \neq n} \frac {Y-x_j}{1-x_j} = n \prod_{j \neq n} \frac {Y-x_j}{1-x_j} = \\ n \frac{1+Y+\ldots+Y^{n-1}}{1+1+\ldots+1} = 1+Y+\ldots+Y^{n-1}$$