# Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 1

## Theorem

Let $r, s, t \in \R, n \in \Z$.

Then:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \left({n - k}\right)} {n - k} \frac r {r - t k} = \binom {r + s - t n} n$

## Proof

For all $n \in \Z$, let $\map P n$ be the proposition:

$\displaystyle \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$

Let the left hand side of this equation be denoted $\tuple {r, s, t, n}$.

Let $n = 0$.

Then:

 $\ds$  $\ds \tuple {r, s, t, 0}$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s + t k} {- k} \frac r {r - t k}$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s + t k} {- k} \frac r {r - t k} \delta_{k 0}$ N Choose Negative Number is Zero: $\dbinom {s + t k} {- k} = 0$ for all $k > 0$ $\ds$ $=$ $\ds \binom r 0 \binom s 0$ Definition of Kronecker Delta $\ds$ $=$ $\ds 1$ Binomial Coefficient with Zero $\ds$ $=$ $\ds \binom {r + s} 0$ Binomial Coefficient with Zero $\ds$ $=$ $\ds \binom {r + s - t n} n$ putting $n = 0$

Thus $\map P 0$ holds.

Let $n < 0$.

Let $n = -m$ where $m > 0$.

Then:

 $\ds$  $\ds \tuple {r, s, t, n}$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {-m - k} } {-m - k} \frac r {r - t k}$ $\ds$ $=$ $\ds 0$ N Choose Negative Number is Zero: $\dbinom {s - t \paren {-m - k} } {-m - k} = 0$ $\ds$ $=$ $\ds \binom {r + s + t m} {-m}$ N Choose Negative Number is Zero: $\dbinom {r + s + t m} {-m} = 0$ for all $m$

Thus $\map P n$ holds for all $n < 0$.

It remains to demonstrate that $\map P n$ holds for all $n > 0$.

The proof continues by strong induction on $n$.

The procedure is to substitute $n - r + n t + m$ for the variable $s$ and establish that the identity holds for all $m \ge 0$.

For all $m \in \Z_{\ge 0}$, let $\map P m$ be the proposition:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {\paren {n - r + n t + m} - t \paren {n - k} } {n - k} \frac r {r - t k} = \binom {r + \paren {n - r + n t + m} - t n} n$

That is:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - r + m + t k} {n - k} \frac r {r - t k} = \binom {n + m} n$

### Basis for the Induction

Consider the special case where $s = n - 1 - r + n t$.

Substituting $n - 1 - r + n t$ for $s$ in the right hand side:

 $\ds \binom {r + s - t n} n$ $=$ $\ds \binom {r + \paren {n - 1 - r + n t} - t n} n$ $\ds$ $=$ $\ds \binom {r + n - 1 - r + n t - t n} n$ $\ds$ $=$ $\ds \binom {n - 1} n$

Substituting $n - 1 - r + n t$ for $s$ in the left hand side:

 $\ds$  $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \dfrac {\paren {r - t k}! \paren {n - 1 - r + t k}! \, r} {k! \paren {r - t k - k}! \paren {n - k}! \paren {k - 1 - r + t k}! \paren {r - t k} }$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \dfrac {\paren {r - t k - 1}! \paren {n - 1 - r + t k}!} {\paren {r - t k - k}! \paren {k - 1 - r + t k}!}$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \prod_{0 \mathop < j \mathop < k} \paren {r - t k - j} \prod_{0 \mathop < j \mathop < n \mathop - k} \paren {n - 1 - r + t k - j}$ $\ds$ $=$ $\ds \sum_{k \mathop \ge 0} \frac r {n!} \binom n k \paren {-1}^{k - 1} \prod_{0 \mathop < j \mathop < k} \paren {-r + t k + j} \prod_{k \mathop \le j \mathop < n} \paren {- r + t k + j}$

The two products give a polynomial of degree $n - 1$ in $k$.

Hence the sum for all $k$ is $0$.

Thus we have:

 $\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - 1 - r + t k} {n - k} \frac r {r - t k}$ $=$ $\ds 0$ $\ds$ $=$ $\ds \binom {n - 1} n$ Definition of Binomial Coefficient

Thus the equation indeed holds for the special case where $s = n - 1 - r + n t$.

$\Box$

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that, if $\map P j$ is true, for all $j$ such that $0 \le j \le m$, then it logically follows that $\map P {m + 1}$ is true.

This is the induction hypothesis:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - r + m + t k} {n - k} \frac r {r - t k} = \binom {n + m} n$

from which it is to be shown that:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {n - r + m + 1 + t k} {n - k} \frac r {r - t k} = \binom {n + m + 1} n$

### Lemma

First a lemma:

Let this hold for $\tuple {r, s, t, n}$:

$\displaystyle \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$

and also for $\tuple {r, s - t, t, n - 1}$.

Then it also holds for $\tuple {r, s + 1, t, n}$.

### Induction Step

This is the induction step:

We have that $\tuple {r, n - 1 - r + n t, t, n}$ holds.

We have also determined that if:

$\tuple {r, s, t, n}$ holds

and:

$\tuple {r, s - t, t, n - 1}$ holds

then:

$\tuple {r, s + 1, t, n}$ holds.

So $\map P m \implies \map P {m + 1}$.

Thus $\tuple {r, s, t, n}$ is shown to hold for infinitely many $s$.

As both the left hand side and right hand side are polynomials in $s$ it follows that $\tuple {r, s, t, n}$ holds for all $s$.

Therefore:

$\displaystyle \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \left({n - k}\right)} {n - k} \frac r {r - t k} = \binom {r + s - t n} n$

for all $r, s, t \in \R, n \in \Z$.

$\blacksquare$