TAOCP 1.2.3 Exercise 33

Let $x_1, x_2, \ldots, x_n$ be distinct numbers, and define, for $0 \le r \le n$, S_r := \sum_{j=1}^n \frac{x_j^r}{\prod_{\substack{1 \le k \le n \\ k \ne j}} (x_j - x_k)}.

taocpmathematicsalgorithmsvolume-1math-hard

Section 1.2.3: Sums and Products

Exercise 33. ▶ [M30] One evening Dr. Matrix discovered some formulas that might even be classed as more remarkable than those of exercise 20:

$$ \begin{aligned} \frac{1}{(a-b)(a-c)} + \frac{1}{(b-a)(b-c)} + \frac{1}{(c-a)(c-b)} &= 0, \[5pt] \frac{a}{(a-b)(a-c)} + \frac{b}{(b-a)(b-c)} + \frac{c}{(c-a)(c-b)} &= 0, \[5pt] \frac{a^2}{(a-b)(a-c)} + \frac{b^2}{(b-a)(b-c)} + \frac{c^2}{(c-a)(c-b)} &= 1, \[5pt] \frac{a^3}{(a-b)(a-c)} + \frac{b^3}{(b-a)(b-c)} + \frac{c^3}{(c-a)(c-b)} &= a+b+c. \end{aligned} $$

Prove that these formulas are a special case of a general law; let $x_1, x_2, \ldots, x_n$ be distinct numbers, and show that

$$ \sum_{j=1}^n \left( x_j^r \bigg/ \prod_{\substack{1 \le k \le n \ k \ne j}} (x_j - x_k) \right) = \begin{cases} 0, & \text{if } 0 \le r < n - 1; \ 1, & \text{if } r = n - 1; \ \sum_{j=1}^n x_j, & \text{if } r = n. \end{cases} $$

Verified: yes
Solve time: 41s

Exercise 1.2.3.33 Solution

Setup

Let $x_1, x_2, \ldots, x_n$ be distinct numbers, and define, for $0 \le r \le n$,

$$ S_r := \sum_{j=1}^n \frac{x_j^r}{\prod_{\substack{1 \le k \le n \ k \ne j}} (x_j - x_k)}. $$

We are asked to show that

$$ S_r = \begin{cases} 0, & 0 \le r < n-1, \ 1, & r = n-1, \ \sum_{j=1}^n x_j, & r = n. \end{cases} $$

This generalizes the specific formulas for $n = 3$ and $r = 0, 1, 2, 3$ given in the exercise. We observe that the denominators are precisely the products of differences appearing in the Lagrange interpolation formula for a polynomial of degree at most $n-1$.

Solution

Consider the Lagrange interpolation polynomial $L(x)$ of degree at most $n-1$ that takes the value $x^r$ at the nodes $x_1, x_2, \ldots, x_n$:

$$ L(x) = \sum_{j=1}^n x_j^r \prod_{\substack{1 \le k \le n \ k \ne j}} \frac{x - x_k}{x_j - x_k}. $$

By construction, $L(x_j) = x_j^r$ for all $1 \le j \le n$. In particular, the coefficient of $x^{n-1}$ in $L(x)$ is

$$ \sum_{j=1}^n \frac{x_j^r}{\prod_{k \ne j} (x_j - x_k)}. $$

This coefficient is exactly $S_r$. Indeed, each term in $L(x)$ contributes to $x^{n-1}$ only from the product of $x$ over all $k \ne j$, which contains $(n-1)$ factors. Denote this product as

$$ \prod_{\substack{1 \le k \le n \ k \ne j}} (x - x_k) = x^{n-1} - (\text{sum of } (n-1) \text{ products of } x_k)x^{n-2} + \cdots. $$

Then the coefficient of $x^{n-1}$ in $\prod_{k \ne j} (x - x_k)$ is $1$. Therefore the contribution of the $j$-th term to $x^{n-1}$ in $L(x)$ is precisely

$$ \frac{x_j^r}{\prod_{k \ne j} (x_j - x_k)}. $$

Hence

$$ S_r = \text{coefficient of } x^{n-1} \text{ in } L(x). $$

Now consider cases according to the degree $r$ of the polynomial $x^r$:

  1. Case $0 \le r < n-1$: The polynomial $x^r$ has degree less than $n-1$. Therefore, its interpolation polynomial $L(x)$ also has degree $r < n-1$, so the coefficient of $x^{n-1}$ is zero. Hence

$$ S_r = 0. $$

  1. Case $r = n-1$: The polynomial $x^{n-1}$ has degree $n-1$. In the Lagrange interpolation formula, the leading term of each basis polynomial $\prod_{k \ne j} \frac{x - x_k}{x_j - x_k}$ is $x^{n-1} / \prod_{k \ne j} (x_j - x_k)$, as argued above. Summing over $j$, the coefficient of $x^{n-1}$ is therefore

$$ S_{n-1} = \sum_{j=1}^n \frac{x_j^{,n-1}}{\prod_{k \ne j} (x_j - x_k)} = 1, $$

because the leading coefficient of $x^{n-1}$ in $x^{n-1}$ is $1$.

  1. Case $r = n$: Consider $x^n$. Its Lagrange interpolation polynomial $L(x)$ has degree at most $n-1$, so $x^n - L(x)$ is a polynomial of degree $n$ vanishing at all $x_j$. Therefore, $x^n - L(x) = c \prod_{j=1}^n (x - x_j)$ for some constant $c$. Expanding both sides, the coefficient of $x^{n-1}$ in $x^n$ is zero, and in $-c \prod_{j=1}^n (x - x_j)$ it is $-c(-1) \sum_{j=1}^n x_j = c \sum_{j=1}^n x_j$. On the other hand, the coefficient of $x^{n-1}$ in $L(x)$ is $S_n$. Equating coefficients of $x^{n-1}$, we obtain

$$ S_n = \sum_{j=1}^n x_j. $$

This completes the argument.

Verification

Check the $n=3$ case given in the exercise:

  • $r=0$: $S_0 = 0$, matches first formula.
  • $r=1$: $S_1 = 0$, matches second formula.
  • $r=2$: $S_2 = 1$, matches third formula.
  • $r=3$: $S_3 = a + b + c$, matches fourth formula.

The computation is consistent.

Notes

This result is equivalent to identifying $S_r$ with the coefficient of $x^{n-1}$ in the Lagrange interpolation polynomial of $x^r$. More generally, for $r \ge n$, $S_r$ equals the sum of elementary symmetric polynomials of degree $r - (n-1)$ in $x_1, \ldots, x_n$. This approach gives a systematic method to compute sums of powers divided by products of differences.

∎

$$ \boxed{ \sum_{j=1}^n \frac{x_j^r}{\prod_{k \ne j} (x_j - x_k)} = \begin{cases} 0, & 0 \le r < n-1, \ 1, & r = n-1, \ \sum_{j=1}^n x_j, & r = n \end{cases} } $$