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

## 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}$