Evaluate the summation involving binomials.

Question

$\sum _{ i=0 }^{ 100 }{\binom{k}{i}}*{\binom{M-k}{100-i}*\frac{k-i}{M-100}}/{\binom{M}{100}}$
I wrote the first few terms but couldn't find any pattern and how to club the terms. Help.

Answer 1

Let's generalize a bit by introducing indices: $$ \sum_i \binom{k}{i} \cdot \binom{M - k}{r - i} \cdot \frac{k - i}{M - r} / \binom{M}{r} = \frac{1}{(M - r) \binom{M}{r}} \cdot \sum_i \binom{k}{i} \binom{M - k}{r - i} \cdot (k - i) $$ We can split the $k - i$ to simplify. So we are interested in sums of the forms: $$ \sum_i \binom{a}{i} \binom{b}{r - i} $$ and $$ \sum_i i \binom{a}{i} \binom{b}{r - i} $$ Now remember: $$ (1 + z)^a = \sum_i \binom{a}{i} z^i \\ z \frac{\mathrm{d}}{\mathrm{d} z} (1 + z)^a = \sum_i i \binom{a}{i} z^i $$ and also: $$ \left(\sum_i u_i \right) \cdot \left( \sum_i v_i \right) = \sum_i \sum_{0 \le j \le i} u_j v_{i - j} $$ In particular: \begin{align} \sum_{r \ge 0} \sum_i \binom{a}{i} \binom{b}{r - i} z^r &= \left(\sum_i \binom{a}{i} z^i \right) \cdot \left(\sum_i \binom{b}{i} z^i \right) \\ &= (1 + z)^a \cdot (1 + z)^b \\ &= (1 + z)^{a + b} \end{align} Comparing coefficients you get Vandermonde's convolution: $$ \sum_i \binom{a}{i} \binom{b}{r - i} = \binom{a + b}{r} $$ For the other half: \begin{align} \sum_r \sum_i i \binom{a}{i} \binom{b}{r - i} z^r &= \left(\sum_i i \binom{a}{i} z^i \right) \cdot \left(\sum_i i \binom{b}{i} z^i \right) \\ &= a z (1 + z)^{a - 1} \cdot (1 + z)^b \\ &= a z (1 + z)^{a + b - 1} \end{align} The coefficient of $z^r$ here is a bit trickier: $$ [z^r] a z (1 + z)^{a + b - 1} = a [z^{r - 1}] (1 + z)^{a + b - 1} = a \binom{a + b - 1}{r - 1} $$ I'm sure you can take it from here.

Answer 2

It's easy \begin{align*} \frac{1}{\binom{M}{100}}\sum_{i=0}^{100}\frac{k-i}{M-100}\binom{k}{i}\binom{M-k}{100-i} &= \frac{k}{M\binom{M-1}{100}}\sum_{i=0}^{100}\binom{k-1}{i}\binom{M-k}{100-i}\\ &= \frac{k}{M\binom{M-1}{100}}\binom{M-1}{100}\\ &= \frac{k}{M} \end{align*}