Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 2
Jump to navigation
Jump to search
Theorem
Let $r, s, t \in \R, n \in \Z$.
Then:
- $\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$
Proof
From Sum over $k$ of $\dbinom {r - k t} k$ by $\dfrac r {r - k t}$ by $z^k$:
- $\ds \sum_k \map {A_k} {r, t} z^k = x^r$
where:
- $\map {A_n} {x, t}$ is the polynomial of degree $n$ defined as:
- $\map {A_n} {x, t} := \dbinom {x - n t} n \dfrac x {x - n t}$
- for $x \ne n t$
- $z = x^{t + 1} - x^t$.
From Sum over $k$ of $\dbinom {r - k t} k$ by $z^k$:
- $\ds \sum_k \dbinom {r - t k} k z^k = \frac {x^{r + 1} } {\paren {t + 1} x - t}$
Thus:
\(\ds \sum_k \map {A_k} {r, t} z^k \sum_k \dbinom {s - t k} k z^k\) | \(=\) | \(\ds \frac {x^r x^{s + 1} } {\paren {t + 1} x - t}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {x^{\paren {r + s} + 1} } {\paren {t + 1} x - t}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_k \dbinom {r + s - t k} k z^k\) |
Equating coefficients of $z$:
\(\ds \sum_k \map {A_k} {r, t} z^k \sum_k \dbinom {s - \paren {n - k} t} k z^{n - k}\) | \(=\) | \(\ds \binom {r + s - n t} n z^n\) | ||||||||||||
\(\ds \sum_k \dbinom {r - k t} k \dfrac r {r - k t} z^k \dbinom {s - \paren {n - k} t} k z^{n - k}\) | \(=\) | \(\ds \binom {r + s - n t} n z^n\) | ||||||||||||
\(\ds \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} k \dfrac r {r - k t}\) | \(=\) | \(\ds \binom {r + s - t n} 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 $27$