Summation by k of Product by r of x plus k minus r over Product by r less k of k minus r
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{k \mathop = 1}^n \paren {\dfrac {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne m} } \paren {x + k - r} } {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne k} } \paren {k - r} } } = 1$
where $1 \le m \le n$ and $x$ is arbitrary.
Example
- $\dfrac {x \paren {x - 2} \paren {x - 3} } {\paren {-1} \paren {-2} \paren {-3} } + \dfrac {\paren {x + 1} \paren {x - 1} \paren {x - 2} } {\paren 1 \paren {-1} \paren {-2} } + \dfrac {\paren {x + 2} x \paren {x - 1} } {\paren 2 \paren 1 \paren {-1} } + \dfrac {\paren {x + 3} \paren {x + 1} x} {\paren 3 \paren 2 \paren 1 } = 1$
Proof
\(\ds \sum_{k \mathop = 1}^n \paren {\dfrac {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne m} } \paren {x + k - r} } {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne k} } \paren {k - r} } }\) | \(=\) | \(\ds \sum_{k \mathop = 1}^n \paren {\dfrac {k^{n - 1} + \map P k} {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne k} } \paren {k - r} } }\) | where $\map P k$ is a polynomial of degree $n - 2$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 1}^n \paren {\dfrac {k^{n - 1} } {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne k} } \paren {k - r} } } + \sum_{k \mathop = 1}^n \paren {\dfrac {\map P k} {\ds \prod_{\substack {1 \mathop \le r \mathop \le n \\ r \mathop \ne k} } \paren {k - r} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 + 0\) | Summation of Powers over Product of Differences |
$\blacksquare$
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 $34$