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
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 1
Let:
- $\ds S = \sum_k \map {A_k} {r, t} \map {A_{n - k} } {s, t}$
Both sides of the statement of the theorem are polynomials in $r$, $s$ and $t$.
Therefore it can be assumed that $r \ne k t \ne s$ for $0 \le k \le n$ or something will become undefined.
By replacing the polynomials $A_n$ with their binomial coefficient definitions, the theorem can be expressed as:
- $\ds S = \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} {n - k} \dfrac r {r - k t} \dfrac s {s - \paren {n - k} t}$
Using the technique of partial fractions:
- $\dfrac 1 {r - k t} \dfrac 1 {s - \paren {n - k} t} = \dfrac 1 {r + s - n t} \paren {\dfrac 1 {r - k t} + \dfrac 1 {s - \paren {n - k} t} }$
Thus:
- $\ds S = \frac s {r + s - n t} \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} {n - k} \dfrac r {r - k t} + \frac r {r + s - n t} \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} {n - k} \dfrac s {s - \paren {n - k} t}$
From Sum over $k$ of $\dbinom {r - t k} k \dbinom {s - t \paren {n - k} } {n - k} \dfrac r {r - t k}$:
- $\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$
for $r, s, t \in \R, n \in \Z$.
Thus we have:
- $S = \dfrac s {r + s - n t} \dbinom {r + s - t n} n + \dfrac r {r + s - n t} \dbinom {s + r - t n} n$
after changing $k$ to $n - k$ in the second term.
That is:
- $S = \dbinom {r + s - n t} n \dfrac {r + s} {r + s - n t}$
which is $\map {A_n} {r + s, t}$.
$\blacksquare$
Proof 2
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$