Sum over k of r-tk Choose k by s-t(n-k) Choose n-k by r over r-tk/Proof 1/Basis for the Induction

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Consider the equation:

$\ds (1): \quad \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$ etc. are binomial coefficients.


Then equation $(1)$ holds for the special case where $s = n - 1 - r + n t$.


Proof

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

$\blacksquare$


Sources