Summation from k to m of r Choose k by s Choose n-k by nr-(r+s)k

From ProofWiki
Jump to navigation Jump to search

Theorem

$\displaystyle \sum_{k \mathop = 0}^m \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} = \paren {m + 1} \paren {n - m} \dbinom r {m + 1} \dbinom s {n - m}$


Proof

The proof proceeds by induction over $m$.

For all $m \in \Z_{\ge 0}$, let $P \left({n}\right)$ be the proposition:

$\displaystyle \sum_{k \mathop = 0}^m \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} = \paren {m + 1} \paren {n - m} \dbinom r {m + 1} \dbinom s {n - m}$


Basis for the Induction

$P \left({0}\right)$ is the case:

\(\displaystyle \sum_{k \mathop = 0}^0 \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k}\) \(=\) \(\displaystyle \dbinom r 0 \dbinom s {n - 0} \paren {n r - \paren {r + s} 0}\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom s n \paren {n r}\) Binomial Coefficient with Zero
\(\displaystyle \) \(=\) \(\displaystyle \paren {0 + 1} \paren {n - 0} \dbinom r {0 + 1} \dbinom s {n - 0}\) Binomial Coefficient with One

Thus $P \left({0}\right)$ is seen to hold.


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $P \left({j}\right)$ is true, where $j \ge 1$, then it logically follows that $P \left({j + 1}\right)$ is true.


So this is the induction hypothesis:

$\displaystyle \sum_{k \mathop = 0}^j \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} = \paren {j + 1} \paren {n - j} \dbinom r {j + 1} \dbinom s {n - j}$


from which it is to be shown that:

$\displaystyle \sum_{k \mathop = 0}^{j + 1} \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} = \paren {j + 2} \paren {n - j - 1} \dbinom r {j + 2} \dbinom s {n - j - 1}$


Induction Step

This is the induction step:

\(\displaystyle \) \(\) \(\displaystyle \sum_{k \mathop = 0}^{j + 1} \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{k \mathop = 0}^j \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} + \dbinom r {j + 1} \dbinom s {n - j - 1} \paren {n r - \paren {r + s} \paren {j + 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {j + 1} \paren {n - j} \dbinom r {j + 1} \dbinom s {n - j} + \dbinom r {j + 1} \dbinom s {n - j - 1} \paren {n r - \paren {r + s} \paren {j + 1} }\)
\(\displaystyle \) \(=\) \(\displaystyle \dbinom r {j + 1} \paren {\paren {j + 1} \paren {n - j} \dbinom s {n - j} + \dbinom s {n - j - 1} \paren {n r - \paren {r + s} \paren {j + 1} } }\) factorising
\(\displaystyle \) \(=\) \(\displaystyle \paren {j + 2} \paren {r - j + 2} \dbinom r {j + 2} \paren {\paren {j + 1} \paren {n - j} \dbinom s {n - j} + \dbinom s {n - j - 1} \paren {n r - \paren {r + s} \paren {j + 1} } }\) Factors of Binomial Coefficient: Corollary 2
\(\displaystyle \) \(=\) \(\displaystyle \paren {j + 2} \paren {r - j + 2} \dbinom r {j + 2} \paren {\dfrac {\paren {j + 1} \paren {n - j} } {\paren {n - j} \paren {s - \paren {n - j} } } \dbinom s {n - j - 1} + \dbinom s {n - j - 1} \paren {n r - \paren {r + s} \paren {j + 1} } }\) Factors of Binomial Coefficient: Corollary 2
\(\displaystyle \) \(=\) \(\displaystyle \paren {j + 2} \paren {r - j + 2} \dbinom r {j + 2} \dbinom s {n - j - 1} \paren {\dfrac {j + 1} {s - n + j} + \paren {n r - \paren {r + s} \paren {j + 1} } }\) simplifying
\(\displaystyle \) \(=\) \(\displaystyle \paren {j + 2} \paren {r - j + 2} \dbinom r {j + 2} \dbinom s {n - j - 1} \paren {\dfrac {j + 1} {s - n + j} + \paren {n r - r j - s j - r - s} }\) simplifying



So $P \left({j}\right) \implies P \left({j + 1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\displaystyle \sum_{k \mathop = 0}^m \dbinom r k \dbinom s {n - k} \paren {n r - \paren {r + s} k} = \paren {m + 1} \paren {n - m} \dbinom r {m + 1} \dbinom s {n - m}$


Sources