Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk
Theorem
Let $r, s, t \in \R, n \in \Z$.
Then:
- $\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$
where $\dbinom {r - t k} k$ and so on are binomial coefficients.
Proof 1
For all $n \in \Z$, let $\map P n$ be the proposition:
- $\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$
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:
- $\ds \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:
- $\ds \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:
- $\ds \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:
- $\ds \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}$:
- $\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$
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:
- $\ds \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$
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$
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}$
- for $x \ne n t$
- $z = x^{t + 1} - x^t$.
From Sum over $k$ of $\dbinom {r - k t} k$ by $z^k$:
- $\ds \sum_k \dbinom {r - t k} k z^k = \frac {x^{r + 1} } {\paren {t + 1} x - t}$
Thus:
\(\ds \sum_k \map {A_k} {r, t} z^k \sum_k \dbinom {s - t k} k z^k\) | \(=\) | \(\ds \frac {x^r x^{s + 1} } {\paren {t + 1} x - t}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \frac {x^{\paren {r + s} + 1} } {\paren {t + 1} x - t}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_k \dbinom {r + s - t k} k z^k\) |
Equating coefficients of $z$:
\(\ds \sum_k \map {A_k} {r, t} z^k \sum_k \dbinom {s - \paren {n - k} t} k z^{n - k}\) | \(=\) | \(\ds \binom {r + s - n t} n z^n\) | ||||||||||||
\(\ds \sum_k \dbinom {r - k t} k \dfrac r {r - k t} z^k \dbinom {s - \paren {n - k} t} k z^{n - k}\) | \(=\) | \(\ds \binom {r + s - n t} n z^n\) | ||||||||||||
\(\ds \sum_k \dbinom {r - k t} k \dbinom {s - \paren {n - k} t} k \dfrac r {r - k t}\) | \(=\) | \(\ds \binom {r + s - t n} n\) |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: $\text {I} \ (26)$