Theorem: Summation of Powers over Product of Differences

:$\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}$

Proof:
=== Definition ===
{{begin-eqn}}
{{eqn | l = \map p x 
      | r = \prod_{k \mathop = 1}^n \paren {x - x_k}
}}
{{eqn | l = \map {p_m} x
      | r = \prod_{\substack {k \mathop = 1 \\ k \mathop \ne m} }^n \paren {x - x_k}
      | c = where $1 \le m \le n$
}}
{{eqn | l = A 
      | r = <nowiki>\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}</nowiki>
      | c = where $\set {x_1, \ldots, x_n}$ is assumed to have distinct elements
}}
{{eqn | l = A_{\vec Y}
      | r = <nowiki>\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}</nowiki>
      | c = Vector $\vec Y$ has entries $y_1,\ldots,y_n$.
}}
{{end-eqn}}
Symbol $\map {\mathbf {Cof } } {M, i, j}$ denotes cofactor $M_{i j}$ of matrix $M$
=== Lemma 1 ===
{{begin-eqn}}
{{eqn | l = \map \det A
      | r = \map {p_m} {x_m} \map {\mathbf {Cof} } {A, m, n}
}}
{{end-eqn}}
'''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:
{{begin-eqn}}
{{eqn | l = <nowiki>\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}</nowiki>
      | r = <nowiki>\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}</nowiki>
}}
{{end-eqn}}
The last column on the right has all components zero except $m$th entry $\map {p_m} {x_m}$.
Apply Laplace Expansion Theorem for Determinants along column $n$.
{{qed|lemma}}
=== Lemma 2 ===
{{begin-eqn}}
{{eqn | n = 1
      | l = \map \det A 
      | r = \prod_{1 \mathop \le i \mathop < j \mathop \le n} \paren {x_j - x_i}
}}   
{{eqn | n = 2
      | l = \map {\mathbf {Cof} } {A, m, n}
      | r = \paren {-1}^{m + n} \prod_{\substack {1 \mathop \le i \mathop < j \mathop \le n \\ i \mathop \ne m \\ j \mathop \ne m} } \paren {x_j - x_i}  
}}   
{{end-eqn}}
'''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} }$.
{{qed|lemma}}
'''Theorem Details''':
The Lemmas change the Theorem's equation to:
{{begin-eqn}}
{{eqn | n = 3
      | l = \sum_{m \mathop = 1}^n {x_m^r} \frac {\map {\mathbf {Cof} } {A, m, n} } {\map \det A}
      | r = <nowiki>\begin{cases}
0 & : 0 \mathop \le r \mathop < n - 1 \\
1 & : r = n - 1 \\
\ds \sum_{j \mathop = 1}^n x_j & : r = n \\
    \end{cases}</nowiki>
}}
{{end-eqn}}
The Laplace Expansion Theorem for Determinants changes identity $(3)$ to:
{{begin-eqn}}
{{eqn | n = 4
      | l = <nowiki>\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}</nowiki>
      | r = <nowiki>\begin{cases}
0 & : 0 \mathop \le r \mathop < n - 1 \\
\map \det A & : r = n - 1 \\
\ds \map \det A \sum_{j \mathop = 1}^n x_j & : r = n \\
    \end{cases}</nowiki>
}}
{{end-eqn}}
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 $\ds \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 \le k \le n$.
Then $x$ is a root of $\ds \map p x = \prod_{k \mathop = 1}^n \paren {x - x_k}$:
{{begin-eqn}}
{{eqn | l = 0
      | r = \map p {x_k}
}}
{{eqn | r = x_k^n - \paren {x_1 + \cdots + x_n} x_k^{n - 1} + \map R {x_k}
}}
{{end-eqn}}
Let:
{{begin-eqn}}
{{eqn | l = c
      | r = x_1 + \cdots + x_n
}}
{{eqn | l = \vec u
      | r = \begin {pmatrix} x_1^n \\ \vdots \\ x_n^n \end{pmatrix}
      | c = Column $n$ of the left side of $(4)$
}}
{{eqn | l = \vec z
      | r = c \begin {pmatrix} x_1^{n - 1} \\ \vdots \\ x_n^{n - 1} \end{pmatrix}
      | c = Constant $c$ times column $n$ of $A$
}}
{{eqn | l = \vec w
      | r = \begin{pmatrix} -\map R {x_1} \\ \vdots \\ -\map R {x_n} \end{pmatrix}
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | n = 5
      | l = \vec u
      | r = \vec z + \vec w
      | c = by equation $x_k^n = c x_k^{n - 1} - \map R {x_k}$
}}
{{eqn | n = 6
      | l = \map \det {A_{\vec z} }
      | r = c \map \det A
      | c = Effect of Elementary Row Operations on Determinant: factoring $c$ from last column of $A_{\vec z}$
}}
{{end-eqn}}
{{begin-eqn}}
{{eqn | n = 7
      | l = \map \det { A_{\vec w} } 
      | r = 0
      | c = Effect of Elementary Row Operations on Determinant: $\vec w$ is a linear combination of columns $1$ to $n - 1$
}}
{{end-eqn}}
The left side of $(4)$:
{{begin-eqn}}
{{eqn | l = \map \det {A_{\vec u} } 
      | r = \map \det {A_{\vec z} } + \map \det {A_{\vec w} }
      | c = by $(5)$ and Determinant as Sum of Determinants
}}
{{eqn | r = c \map \det A + 0
      | c = by $(6)$ and $(7)$
}}
{{eqn | r = \map \det A \sum_{i \mathop = 1}^n x_i
      | c = definition of $c$
}}
{{end-eqn}}
{{qed}}