# How to prove the following discovery of Euler?

There exists a series of formulas. \begin{align*} \ & \dfrac{1}{(a-b)(a-c)}+\dfrac{1}{(b-a)(b-c)}+\dfrac{1}{(c-a)(c-b)} = 0, \\ \ & \dfrac{a}{(a-b)(a-c)}+\dfrac{b}{(b-a)(b-c)}+\dfrac{c}{(c-a)(c-b)} = 0, \\ \ & \dfrac{a^2}{(a-b)(a-c)}+\dfrac{b^2}{(b-a)(b-c)}+\dfrac{c^2}{(c-a)(c-b)} = 1, \\ \ & \dfrac{a^3}{(a-b)(a-c)}+\dfrac{b^3}{(b-a)(b-c)}+\dfrac{c^3}{(c-a)(c-b)} = a+b+c. \end{align*} They are related to a fantastic discovery made by Leonhard Euler: if $$x_1,x_2,\ldots,x_n$$ are distinct numbers, then the following holds: $$\sum_{j=1}^n\left(\left. x_j^r\right/ \prod_{\substack{1\leqslant k\leqslant n \\ k\neq j}}(x_j-x_k)\right) = \begin{cases}0, & \text{if } 0\leqslant r < n-1; \\ 1, & \text{if } r=n-1; \\ \sum_{j=1}^nx_j, & \text{if } r=n.\end{cases}$$

Does someone know how to prove it rigorously? I've seen weird ways which are presumably wrong and unnecessarily complex, but I'm looking for a simple proof.

• Who's to say a proof being complex necessarily implies it is wrong? I've seen some pretty scary proofs of even basic theorems like Pythagoras' theorem, after all... Jan 15, 2023 at 22:45
• @Mariano Suárez-Álvarez I don't understand the meaning of your sentence "How do you measure the necessity of the complexity of a wrong proof" Jan 15, 2023 at 23:26
• Does this answer your question? Exercise 1.2.3-33 from TAOCP -- Prove a formula by induction. Jan 15, 2023 at 23:40

Consider the Vandermonde-like determinant

$$V_r = \det \left[ \begin{array}{ccccc} 1 & 1 & 1 & \cdots & 1 \\ x_1 & x_2 & x_3 & \cdots & x_n \\ x_1^2 & x_2^2 & x_3^2 & \cdots & x_n^2 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_1^{n-2} & x_2^{n-2} & x_3^{n-2} & \cdots & x_n^{n-2} \\ x_1^r & x_2^r & x_3^r & \cdots & x_n^r \end{array} \right].$$

If $$0 \le r \le n-2$$ then the last row is equal to one of the others so the determinant is zero. If $$r = n-1$$ we get the usual Vandermonde determinant

$$V_{n-1} = \prod_{1 \le i < j \le n} (x_j - x_i)$$

(up to possibly a sign that I haven't checked carefully). The usual proof of this is to observe that if $$x_i = x_j$$ for any $$i \neq j$$ then two of the rows of the matrix are identical so the determinant vanishes, which establishes that the RHS divides the LHS. They also have the same degree so one is a scalar multiple of the other and then it remains to consider the coefficient of any monomial to compute this constant.

Finally, if $$r = n$$ then the same argument as above establishes that $$V_n$$ is a polynomial of degree $${n \choose 2} + 1$$ which is divisible by the Vandermonde determinant $$V_{n-1}$$, so the ratio $$\frac{V_n}{V_{n-1}}$$ is a homogeneous polynomial in the $$x_i$$ of degree $$1$$. Moreover, because $$V_r$$ is antisymmetric (if the $$x_i$$ are permuted then $$V_r$$ changes by the sign of the permutation), this ratio is a symmetric polynomial of the $$x_i$$, so it must be a scalar multiple of $$e_1 = x_1 + x_2 + \dots + x_n$$. Considering the coefficient of any monomial as above gives

$$V_n = \left( \sum_{i=1}^n x_i \right) V_{n-1}$$

(again, up to possibly a sign that I haven't checked carefully). Finally, I claim that

$$\begin{eqnarray*} V_r &=& \sum_{i=1}^n x_i^r (-1)^{n+i}\prod_{1 \le j < k \le n, j, k \neq i} (x_k - x_j) \\ &=& \sum_{i=1}^n \frac{x_i^r}{\prod_{1 \le j \le n, j \neq i} (x_i - x_j)} V_{n-1} \end{eqnarray*}$$

so this sequence of identities for $$V_r$$ is equivalent to the desired sequence of identities multiplied by the Vandermonde determinant $$V_{n-1}$$. This last identity follows by cofactor expansion along the last row, together with the observation that the cofactors are all Vandermonde determinants but with one of the variables $$x_i$$ omitted. (Again this is all possibly up to signs that I haven't checked carefully.)

This is all a special case of Jacobi's bialternant formula for the Schur polynomials but you don't need to know that to understand this proof.