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

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof

Evaluating the equation for $\tuple {r, s - t, t, n - 1}$:

\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {\paren {s - t} - t \paren {\paren {n - 1} - k} } {\paren {n - 1} - k} \frac r {r - t k}\) \(=\) \(\ds \binom {r + \paren {s - t} - t \paren {n - 1} } {n - 1}\)
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t - t n + t + t k} {n - k - 1} \frac r {r - t k}\) \(=\) \(\ds \binom {r + s - t - t n + 1} {n - 1}\)
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s - t \paren {n - k} } {n - k - 1} \frac r {r - t k}\) \(=\) \(\ds \binom {r + s - t n} {n - 1}\)

Adding the equation in $\tuple {r, s, t, n}$:

\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \paren {\binom {s - t \paren {n - k} } {n - k - 1} + \binom {s - t \paren {n - k} } {n - k} } \frac r {r - t k}\) \(=\) \(\ds \binom {r + s - t n} {n - 1} + \binom {r + s - t n} n\)
\(\ds \sum_{k \mathop \ge 0} \binom {r - t k} k \binom {s + 1 - t \paren {n - k} } {n - k } \frac r {r - t k}\) \(=\) \(\ds \binom {r + s + 1 - t n} n\) Pascal's Rule

Hence the equation holds for $\tuple {r, s + 1, t, n}$

$\blacksquare$


Sources