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

From ProofWiki
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 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$