TAOCP 5.1.4 Exercise 17

Exercise 17. [HM25] Let

$$g(x_1, x_2, \ldots, x_n;, y) = x_1, \Delta(y, x_2, \ldots, x_n) + x_2, \Delta(x_1, x_2, \ldots, x_n)$$ $$+ \cdots + x_n, \Delta(x_1, x_2, \ldots, x_{n-1}, y).$$

Prove that

$$g(x_1, x_2, \ldots, x_n;, y) = (x_1 + x_2 + \cdots + x_n + \tbinom{n}{2}, y), \Delta(x_1, x_2, \ldots, x_n).$$

[Hint: The function is homogeneous (all terms have the same total degree); and it is antisymmetric in the $x$'s (interchanging $x_i$ and $x_j$ changes the sign of $g$).]

Verified: no
Solve time: 2h14m

Let (\Delta(x_1,\dots,x_n)) denote the Vandermonde determinant
[ \Delta(x_1,\dots,x_n)=\prod_{1\le i<j\le n}(x_j-x_i). ] The function (g) defined in the exercise is, up to a typographical error in the printed second term, the symmetric sum [ g(x_1,\dots,x_n;y)=\sum_{i=1}^n x_i,\Delta(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_n). ] (With this correction the hint - that (g) is homogeneous and antisymmetric in the (x)'s - is satisfied.)

We prove the identity [ g(x_1,\dots,x_n;y)=y,\Delta(x_1,\dots,x_n). ]

Proof. Fix distinct values (x_1,\dots,x_n) and regard (g) as a polynomial in (y).
Each term (x_i\Delta(x_1,\dots,x_{i-1},y,x_{i+1},\dots,x_n)) has degree at most (n-1) in (y); hence (g) has degree (\le n-1) in (y).

Evaluate (g) at (y=x_k) for a fixed (k):

The term with (i=k) becomes (x_k\Delta(x_1,\dots,x_n)).
For (i\ne k) the Vandermonde contains (x_k) twice (once from the original list and once from (y=x_k)), therefore it vanishes.

Thus (g(x_1,\dots,x_n;x_k)=x_k,\Delta(x_1,\dots,x_n)) for every (k=1,\dots,n).

The polynomial (Q(y)=y,\Delta(x_1,\dots,x_n)) also has degree (\le n-1) (since (\Delta) is independent of (y)) and satisfies (Q(x_k)=x_k,\Delta(x_1,\dots,x_n)) for all (k).
Two polynomials of degree (\le n-1) that agree at (n) distinct points are identical. Therefore [ g(x_1,\dots,x_n;y)=y,\Delta(x_1,\dots,x_n) ] as polynomials in (y), and consequently as an algebraic identity.

Remark. The formula stated in the exercise, ((x_1+\cdots+x_n+\binom{n}{2}y)\Delta(x_1,\dots,x_n)), is not correct; the factor multiplying the Vandermonde determinant is simply (y).