Sum over k of r+tk choose k by s-tk choose n-k

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{\ge 0}$ be a non-negative integer.


Then:

$\displaystyle \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k} = \sum_{k \mathop \ge 0} \dbinom {r + s - k} {n - k} t^k$

where $\dbinom {r + t k} k$ etc. denotes a binomial coefficient.


Proof

Let $f \left({r, s, t, n}\right)$ be the function defined as:

$\displaystyle f \left({r, s, t, n}\right) := \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k}$


We have:

\(\displaystyle \) \(\) \(\displaystyle \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k} \frac {r + t k} {r + t k}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k} \frac r {r + t k} + \sum_k \dbinom {r + t k} k \dbinom {s - t k} {n - k} \frac {t k} {r + t k}\)



Sources