Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 1/Basis for the Induction
Jump to navigation
Jump to search
Theorem
Let $r, s, t \in \R, n \in \Z$.
Consider the equation:
- $\ds (1): \quad \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$
where $\dbinom {r - t k} k$ etc. are binomial coefficients.
Then equation $(1)$ holds for the special case where $s = n - 1 - r + n t$.
Proof
Substituting $n - 1 - r + n t$ for $s$ in the right hand side:
\(\ds \binom {r + s - t n} n\) | \(=\) | \(\ds \binom {r + \paren {n - 1 - r + n t} - t n} n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \binom {r + n - 1 - r + n t - t n} n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \binom {n - 1} n\) |
Substituting $n - 1 - r + n t$ for $s$ in the left hand side:
\(\ds \) | \(\) | \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \dfrac {\paren {r - t k}! \paren {n - 1 - r + t k}! \, r} {k! \paren {r - t k - k}! \paren {n - k}! \paren {k - 1 - r + t k}! \paren {r - t k} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \dfrac {\paren {r - t k - 1}! \paren {n - 1 - r + t k}!} {\paren {r - t k - k}! \paren {k - 1 - r + t k}!}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \prod_{0 \mathop < j \mathop < k} \paren {r - t k - j} \prod_{0 \mathop < j \mathop < n \mathop - k} \paren {n - 1 - r + t k - j}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \paren {-1}^{k - 1} \prod_{0 \mathop < j \mathop < k} \paren {-r + t k + j} \prod_{k \mathop \le j \mathop < n} \paren {- r + t k + j}\) |
The two products give a polynomial of degree $n - 1$ in $k$.
Hence the sum for all $k$ is $0$.
Thus we have:
\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}\) | \(=\) | \(\ds 0\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \binom {n - 1} n\) | Definition of Binomial Coefficient |
Thus the equation indeed holds for the special case where $s = n - 1 - r + n t$.
$\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 $22$