Summation of Powers over Product of Differences/Proof 1

From ProofWiki
Jump to navigation Jump to search

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


Proof

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$



This article, or a section of it, needs explaining.
In particular: I found the workings of this on a piece of paper dating back from when I was ploughing my way through Knuth 15 years ago. I can't follow much of it any more and I'm not sure how much of it is accurate. If anyone cares to rewrite it in the places where it is wrong, and/or add lemmas explaining some of the larger logical jumps, then please feel free.
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Explain}} from the code.



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

Retrieved from "https://proofwiki.org/w/index.php?title=Summation_of_Powers_over_Product_of_Differences/Proof_1&oldid=662634"