Sum over k of r-kt Choose k by r over r-kt by s-(n-k)t Choose n-k by s over s-(n-k)t/Proof 2
Jump to navigation
Jump to search
Theorem
For $n \in \Z_{\ge 0}$:
- $\ds \sum_k \map {A_k} {r, t} \map {A_{n - k} } {s, t} = \map {A_n} {r + s, t}$
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}$
where $x \ne n t$.
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$
and:
- $\ds \sum_k \map {A_k} {s, t} z^k = x^s$
Hence:
\(\ds x^{r + s}\) | \(=\) | \(\ds \sum_k \map {A_k} {r, t} z^k \sum_k \map {A_k} {s, t} z^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_k \map {A_k} {r + s, t} z^k\) |
Taking the $z^n$ coefficient:
\(\ds \sum_k \map {A_k} {r, t} z^k \sum_k \map {A_{n - k} } {s, t} z^{n - k}\) | \(=\) | \(\ds \map {A_n} {r + s, t} z^n\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \sum_k \map {A_k} {r, t} \sum_k \map {A_{n - k} } {s, t}\) | \(=\) | \(\ds \map {A_n} {r + s, 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 $27$