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

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

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