Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 1/Lemma
Jump to navigation
Jump to search
Theorem
Let this hold for $\tuple {r, s, t, n}$:
- $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + s - t n} n$
and also for $\tuple {r, s - t, t, n - 1}$.
Then it also holds for $\tuple {r, s + 1, t, n}$.
Proof
Evaluating the equation for $\tuple {r, s - t, t, n - 1}$:
\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {\paren {s - t} - t \paren {\paren {n - 1} - k} } {\paren {n - 1} - k} \frac r {r - t k}\) | \(=\) | \(\ds \binom {r + \paren {s - t} - t \paren {n - 1} } {n - 1}\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t - t n + t + t k} {n - k - 1} \frac r {r - t k}\) | \(=\) | \(\ds \binom {r + s - t - t n + 1} {n - 1}\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k - 1} \frac r {r - t k}\) | \(=\) | \(\ds \binom {r + s - t n} {n - 1}\) |
Adding the equation in $\tuple {r, s, t, n}$:
\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \paren {\binom {s - t \paren {n - k} } {n - k - 1} + \binom {s - t \paren {n - k} } {n - k} } \frac r {r - t k}\) | \(=\) | \(\ds \binom {r + s - t n} {n - 1} + \binom {r + s - t n} n\) | ||||||||||||
\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s + 1 - t \paren {n - k} } {n - k } \frac r {r - t k}\) | \(=\) | \(\ds \binom {r + s + 1 - t n} n\) | Pascal's Rule |
Hence the equation holds for $\tuple {r, s + 1, t, n}$
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $23$