Summation of Powers over Product of Differences
Theorem
- $\ds \sum_{j \mathop = 1}^n \begin{pmatrix} {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } \end{pmatrix} = \begin{cases} 0 & : 0 \le r < n - 1 \\ 1 & : r = n - 1 \\ \ds \sum_{j \mathop = 1}^n x_j & : r = n \end{cases}$
Example
\(\ds \frac 1 {\paren {a - b} \paren {a - c} } + \frac 1 {\paren {b - a} \paren {b - c} } + \frac 1 {\paren {c - a} \paren {c - b} }\) | \(=\) | \(\ds 0\) | ||||||||||||
\(\ds \frac a {\paren {a - b} \paren {a - c} } + \frac b {\paren {b - a} \paren {b - c} } + \frac c {\paren {c - a} \paren {c - b} }\) | \(=\) | \(\ds 0\) | ||||||||||||
\(\ds \frac {a^2} {\paren {a - b} \paren {a - c} } + \frac {b^2} {\paren {b - a} \paren {b - c} } + \frac {c^2} {\paren {c - a} \paren {c - b} }\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \frac {a^3} {\paren {a - b} \paren {a - c} } + \frac {b^3} {\paren {b - a} \paren {b - c} } + \frac {c^3} {\paren {c - a} \paren {c - b} }\) | \(=\) | \(\ds a + b + c\) |
Proof 1
The proof proceeds by induction.
For all $n \in \Z_{\ge 0}$, let $\map P n$ be the proposition:
- $\ds S_n := \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } = \begin{cases} 0 & : 0 \le r < n - 1 \\ 1 & : r = n - 1 \\ \ds \sum_{j \mathop = 1}^n x_j & : r = n \end{cases}$
Edge Cases
$\map P 0$ is a vacuous summation:
- $\ds S_0 := \sum_{j \mathop = 1}^0 \paren {\dfrac { {x_j}^0} {\ds \prod_{\substack {1 \mathop \le k \mathop \le 0 \\ k \mathop \ne j} } \paren {x_j - x_k} } } = 0 = \sum_{j \mathop = 1}^0 x_0$
which is seen to hold.
$\map P 1$ is the case:
\(\ds \sum_{j \mathop = 1}^1 \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le 1 \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | \(=\) | \(\ds \dfrac { {x_1}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le 1 \\ k \mathop \ne 1} } \paren {x_1 - x_k} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac { {x_1}^r} 1\) | as the continued product is vacuous | |||||||||||
\(\ds \) | \(=\) | \(\ds {x_1}^r\) | simplification | |||||||||||
\(\ds \) | \(=\) | \(\ds \begin{cases} 1 & : r = 0 \\ x_1 & : r = 1 \end{cases}\) |
This is also seen to hold.
Basis for the Induction
$\map P 2$ is the case where $n = 2$:
\(\ds S_2\) | \(=\) | \(\ds \sum_{j \mathop = 1}^2 \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le 2 \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac { {x_1}^r} {x_1 - x_2} + \frac { {x_2}^r} {x_2 - x_1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac { {x_1}^r - {x_2}^r} {x_1 - x_2}\) |
When $0 \le r < n - 1$, it must be that $r = 0$:
\(\ds S_2\) | \(=\) | \(\ds \frac {1 - 1} {x_1 - x_2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 0\) |
When $r = n - 1 = 1$:
\(\ds S_2\) | \(=\) | \(\ds \frac {x_1 - x_2} {x_1 - x_2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1\) |
When $r = n = 2$:
\(\ds S_2\) | \(=\) | \(\ds \frac { {x_1}^2 - {x_2}^2} {x_1 - x_2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {\paren {x_1 + x_2} \paren {x_1 - x_2} } {x_1 - x_2}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x_1 + x_2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{j \mathop = 1}^2 x_j\) |
Thus in all cases, $\map P 2$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $\map P m$ is true, where $m \ge 2$, then it logically follows that $\map P {m + 1}$ is true.
So this is the induction hypothesis:
- $\ds \sum_{j \mathop = 1}^m \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le m \\ k \mathop \ne j} } \paren {x_j - x_k} } } = \begin{cases} 0 & : 0 \le r < m - 1 \\ 1 & : r = m - 1 \\ \ds \sum_{j \mathop = 1}^m x_j & : r = m \end{cases}$
from which it is to be shown that:
- $\ds \sum_{j \mathop = 1}^{m + 1} \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le m + 1 \\ k \mathop \ne j} } \paren {x_j - x_k} } } = \begin{cases} 0 & : 0 \le r < m \\ 1 & : r = m \\ \ds \sum_{j \mathop = 1}^{m + 1} x_j & : r = {m + 1} \end{cases}$
Induction Step
This is the induction step:
For $n > 2$, let the formula be rewritten:
\(\ds S_n\) | \(=\) | \(\ds \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {x_n - x_{n - 1} } \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r \paren {x_n - x_{n - 1} } } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {x_n - x_{n - 1} } \paren {\sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r \paren {x_j - x_n} } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } - \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r \paren {x_j - x_{n - 1} } } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } }\) |
So:
\(\ds S_{n + 1}\) | \(=\) | \(\ds \frac 1 {x_{n + 1} - x_n} \paren {\sum_{j \mathop = 1}^{n + 1} \paren {\dfrac { {x_j}^r \paren {x_j - x_{n + 1} } } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n + 1 \\ k \mathop \ne j} } \paren {x_j - x_k} } } - \sum_{j \mathop = 1}^{n + 1} \paren {\dfrac { {x_j}^r \paren {x_j - x_n} } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n + 1 \\ k \mathop \ne j} } \paren {x_j - x_k} } } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 {x_{n + 1} - x_n} \paren {\sum_{\substack {1 \mathop \le j \mathop \le n + 1 \\ j \mathop \ne n} } \paren {\dfrac { {x_j}^r } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n + 1 \\ k \mathop \ne j \\ k \mathop \ne n} } \paren {x_j - x_k} } } - \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } }\) | as both parts are the original sum |
When $r < n$, both parts are equal to $0$ or $1$ by the induction hypothesis.
Thus either:
- $S_{n + 1} = \dfrac 1 {x_{n + 1} - x_n} \paren {1 - 1} = 0$
or:
- $S_{n + 1} = \dfrac 1 {x_{n + 1} - x_n} \paren {0 - 0} = 0$
and so $\map P {m + 1}$ holds for $r < n$.
When $r = n$:
\(\ds \sum_{\substack {1 \mathop \le j \mathop \le n + 1 \\ j \mathop \ne n} } \paren {\dfrac { {x_j}^r } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n + 1 \\ k \mathop \ne j \\ k \mathop \ne n} } \paren {x_j - x_k} } }\) | \(=\) | \(\ds \sum_{\substack {1 \mathop \le j \mathop \le n + 1 \\ j \mathop \ne n} } x_j\) | ||||||||||||
\(\ds \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | \(=\) | \(\ds \sum_{j \mathop = 1}^n x_j\) |
Thus:
- $S_{n + 1} = \dfrac 1 {x_{n + 1} - x_n} \paren {x_{n + 1} - x_n} = 1$
and so $\map P {m + 1}$ holds for $r = n$.
Now:
\(\ds \sum_{j \mathop = 1}^n \paren {\dfrac {\ds \prod_{k \mathop = 1}^n \paren {x_j - x_k} } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | \(=\) | \(\ds 0\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^n - \paren {x_1 + \cdots + x_n} {x_j}^{n + 1} + \map P {x_j} } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | where $\map P {x_j}$ is a polynomial of degree $n - 2$ | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^n} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } }\) | \(=\) | \(\ds \sum_{l \mathop = 1}^n \paren {\sum_{j \mathop = 1}^n x_l \paren {\dfrac { {x_j}^{n - 1} } {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } }\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{l \mathop = 1}^n x_l\) |
Thus $\map P {m + 1}$ holds for $r = n + 1$.
So $\map P m \implies \map P {m + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\displaystyle \forall n \in \Z_{\ge 0}: \sum_{j \mathop = 1}^n \paren {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } = \begin{cases} 0 & : 0 \le r < n - 1 \\ 1 & : r = n - 1 \\ \ds \sum_{j \mathop = 1}^n x_j & : r = n \end{cases}$
$\blacksquare$
Proof 2
- $\ds \sum_{j \mathop = 1}^n \begin {pmatrix} {\dfrac { {x_j}^r} {\ds \prod_{\substack {1 \mathop \le k \mathop \le n \\ k \mathop \ne j} } \paren {x_j - x_k} } } \end {pmatrix} = \dfrac 1 {2 \pi i} \int \limits_{\size z \mathop = R} \dfrac {z^r \rd z} {\paren {z - z_1} \cdots \paren {z - z_n} }$
where $R > \size {z_1}, \ldots, \size {z_n}$.
The Laurent series of the integrand converges uniformly on $\size z = R$:
\(\ds \) | \(\) | \(\ds z^{r - n} \paren {\dfrac 1 {1 - x_1 / z} } \cdots \paren {\dfrac 1 {1 - x_n / z} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds z^{r - n} + \paren {x_1 + \cdots x_n} z^{r - n - 1} + \paren {x_1^2 + x_1 x_2 + \cdots} z^{r - n - 2} + \cdots\) |
On integrating term my term, everything vanishes except the coefficient of $z^{-1}$.
Thus:
- $\ds \sum_{\substack {j_1 \mathop + \mathop \cdots \mathop + j_n \mathop = r \mathop - n \mathop + 1 \\ j_1, \mathop \ldots j_n \mathop \ge 0} } {x_1}^{j_1} {x_2}^{j_2} \cdots {x_n}^{j_n}$
$\blacksquare$
Proof 3
Definition
\(\ds \map p x\) | \(=\) | \(\ds \prod_{k \mathop = 1}^n \paren {x - x_k}\) | ||||||||||||
\(\ds \map {p_m} x\) | \(=\) | \(\ds \prod_{k \mathop = 1, \, k \mathop \ne m}^n \paren {x - x_k},\quad 1 \le m \le n\) | ||||||||||||
\(\ds A\) | \(=\) | \(\ds \begin{pmatrix} 1 & x_1 & \cdots & x_1^{n - 2} & x_1^{n - 1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & \cdots & x_n^{n - 2} & x_n^{n - 1} \\ \end{pmatrix}\) |
where $\set {x_1, \ldots, x_n}$ is assumed to have distinct elements | |||||||||||
\(\ds A_{\vec Y}\) | \(=\) | \(\ds \begin{pmatrix}
1 & x_1 & \cdots & x_1^{n - 2} & y_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & \cdots & x_n^{n -2} & y_n \\ \end{pmatrix}\) |
Vector $\vec Y$ has entries $y_1,\ldots,y_n$. |
Symbol $\map {\mathbf {Cof } } {M, i, j}$ denotes cofactor $M_{i j}$ of matrix $M$
Lemma 1
\(\ds \map \det A\) | \(=\) | \(\ds \map {p_m} {x_m} \map {\mathbf {Cof} } {A, m, n}\) |
Proof of Lemma 1
By Effect of Elementary Row Operations on Determinant, the determinant of $A$ is unchanged by adding a linear combination of the first $n - 1$ columns to the last column.
Let $\map f x$ be the monic polynomial $\map {p_m} x = x^{n - 1} + $ lower power terms.
Then:
\(\ds \det \begin {pmatrix}
1 & x_1 & \cdots & x_1^{n - 2} & x_1^{n - 1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & \cdots & x_n^{n - 2} & x_n^{n - 1} \\ \end {pmatrix}\) |
\(=\) | \(\ds \det \begin {pmatrix}
1 & x_1 & \cdots & x_1^{n - 2} & \map f {x_1} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & \cdots & x_n^{n - 2} & \map f {x_n} \\ \end {pmatrix}\) |
The last column on the right has all components zero except $m$th entry $\map {p_m} {x_m}$.
Apply cofactor expansion along column $n$.
$\Box$
Lemma 2
\(\text {(1)}: \quad\) | \(\ds \map \det A\) | \(=\) | \(\ds \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}\) | |||||||||||
\(\text {(2)}: \quad\) | \(\ds \map {\mathbf {Cof} } {A, m, n}\) | \(=\) | \(\ds \paren {-1}^{m + n} \prod_{1 \mathop \le i \mathop < j \mathop \le n, \, i \mathop \ne m, \, j \mathop \ne m} \paren {x_j - x_i}\) |
Proof of Lemma 2:
Value of Vandermonde Determinant establishes $(1)$.
To prove (2), let:
- $\set {y_1, \ldots, y_{n - 1} } = \set {x_1, \ldots, x_n} \setminus \set {x_m}$
then apply $(1)$ with $\set {x_1, \ldots, x_n}$ replaced by $\set {y_1, \ldots, y_{n - 1} }$.
$\Box$
Theorem Details:
The Lemmas change the Theorem's equation to:
\(\text {(3)}: \quad\) | \(\ds \sum_{m \mathop = 1}^n {x_m^r} \, \dfrac {\map {\mathbf {Cof} } {A, m, n} } {\map \det A}\) | \(=\) | \(\ds \begin{cases}
0 & : 0 \mathop \le r \mathop < n - 1 \\ 1 & : r = n - 1 \\ \sum_{j \mathop = 1}^n x_j & : r = n \\ \end{cases}\) |
Cofactor expansion changes identity $(3)$ to:
\(\text {(4)}: \quad\) | \(\ds \det \begin{pmatrix}
1 & x_1 & \cdots & x_1^{n - 2} & x_1^r \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 1 & x_n & \cdots & x_n^{n - 2} & x_n^r \\ \end{pmatrix}\) |
\(=\) | \(\ds \map \det A \begin{cases}
0 & : 0 \mathop \le r \mathop < n - 1 \\ 1 & : r = n - 1 \\ \sum_{j \mathop = 1}^n x_j & : r = n \\ \end{cases}\) |
The proof is divided into three cases.
Case 1: $0 \mathop \le r \mathop \le n - 2$:
The determinant on the left in $(4)$ is zero by Square Matrix with Duplicate Rows has Zero Determinant.
Case 2: $r = n - 1$:
The determinant on the left in $(4)$ is $\map \det A$.
Case 3: $r = n$:
Expand $\map p x = \prod_{k \mathop = 1}^n \paren {x - x_k}$ by Taylor's Theorem with remainder $R$ of degree $n - 2$:
- $\map p x = x^n - \paren {x_1 + \cdots + x_n} x^{n - 1} + \map R x$
Let $x = x_k$ for $1 \mathop \le k \mathop \le n$.
Then $x$ is a root of $\map p x = \prod_{k \mathop = 1}^n \paren {x - x_k}$:
\(\ds 0\) | \(=\) | \(\ds \map p {x_k}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds x_k^n - \paren {x_1 + \cdots + x_n} x_k^{n - 1} + \map R {x_k}\) |
Let:
\(\ds c\) | \(=\) | \(\ds x_1 + \cdots + x_n\) | ||||||||||||
\(\ds \vec u\) | \(=\) | \(\ds \begin {pmatrix} x_1^n \\ \vdots \\ x_n^n \end{pmatrix}\) | Column $n$ of the left side of $(4)$ | |||||||||||
\(\ds \vec z\) | \(=\) | \(\ds c \begin {pmatrix} x_1^{n - 1} \\ \vdots \\ x_n^{n - 1} \end{pmatrix}\) | Constant $c$ times column $n$ of $A$ | |||||||||||
\(\ds \vec w\) | \(=\) | \(\ds \begin{pmatrix} -\map R {x_1} \\ \vdots \\ -\map R {x_n} \end{pmatrix}\) |
Then:
\(\text {(5)}: \quad\) | \(\ds \vec u\) | \(=\) | \(\ds \vec z + \vec w\) | by equation $x_k^n = c x_k^{n - 1} - \map R {x_k}$ | ||||||||||
\(\text {(6)}: \quad\) | \(\ds \map \det {A_{\vec z} }\) | \(=\) | \(\ds c \map \det A\) | Effect of Elementary Row Operations on Determinant: factoring $c$ from last column of $A_{\vec z}$ |
\(\text {(7)}: \quad\) | \(\ds \det \paren { A_{\vec w} }\) | \(=\) | \(\ds 0\) | Effect of Elementary Row Operations on Determinant: $\vec w$ is a linear combination of columns $1$ to $n - 1$ |
The left side of $(4)$:
\(\ds \map \det {A_{\vec u} }\) | \(=\) | \(\ds \map \det {A_{\vec z} } + \map \det {A_{\vec w} }\) | by $(5)$ and Determinant as Sum of Determinants | |||||||||||
\(\ds \) | \(=\) | \(\ds c \map \det A + 0\) | by $(6)$ and $(7)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \map \det A \displaystyle \sum_{i \mathop = 1}^n x_i\) | definition of $c$ |
$\blacksquare$
Historical Note
The result Summation of Powers over Product of Differences was discussed by Leonhard Paul Euler in a letter to Christian Goldbach in $1762$.
He subsequently published it in his Institutiones Calculi Integralis, Volume 2 of $1769$.
The proof involving complex analysis was devised in $1857$ by James Joseph Sylvester.
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.3$: Sums and Products: Exercise $33$