I am asked to find the following sum:$$\sum_{i=0}^{100}\binom{k}{i}\binom{M-k}{100-i}\frac{(k-i)}{M-100}$$

The first two terms in the expression i.e, the binomial coefficients is actually $\binom{M}{100}$ as $\binom{k}{i}$ is the coefficient of $x^i$ in $(1+x)^k$ and $\binom{M-k}{100-i}$ is the coefficient of $x^{100-i}$ in $(1+x)^{M-k}$.

Simplifying things I get an answer which is no was close to the actual answer.

  • $\begingroup$ What's the relation between $M$ and $k$ ?. $M < k$ ?. $M \geq k$ ?. $M$ and/or $k$ $\in \mathbb{Z}$ or $\mathbb{N}$ ?. $\endgroup$ – Felix Marin Jul 14 '17 at 13:35

Note that by Vandermonde's identity, $$\sum_{i=0}^{100}\binom{k}{i}\binom{M-k}{100-i}k=k\sum_{i=0}^{100}\binom{k}{i}\binom{M-k}{100-i}=k\binom{M}{100}$$ and $$\sum_{i=0}^{100}\binom{k}{i}\binom{M-k}{100-i}i=\sum_{i=1}^{100}\frac{k}{i}\binom{k-1}{i-1}\binom{M-k}{100-i}i=k\sum_{i=1}^{100}\binom{k-1}{i-1}\binom{M-k}{99-(i-1)}\\ =k\sum_{j=0}^{99}\binom{k-1}{j}\binom{M-k}{99-j}=k\binom{M-1}{99}=\frac{k100}{M}\binom{M}{100}.$$ Hence $$\sum_{i=0}^{100}\binom{k}{i}\binom{M-k}{100-i}\frac{(k-i)}{M-100}= \frac{1}{M-100}\left(k\binom{M}{100}-\frac{k100}{M}\binom{M}{100}\right)= \frac{k}{M}\binom{M}{100}.$$

  • $\begingroup$ Have edited the question again. Please take a look. $\endgroup$ – Epsilon zero Jul 14 '17 at 11:18
  • $\begingroup$ @Anuran Chowdhury Ok. My hint holds also in this case. $\endgroup$ – Robert Z Jul 14 '17 at 11:20
  • $\begingroup$ Thanks for the help @Robert Z ! I will let you know in a while. $\endgroup$ – Epsilon zero Jul 14 '17 at 11:32
  • $\begingroup$ Have you got (k/m)C(m,100)? I did it but tediously $\endgroup$ – Epsilon zero Jul 14 '17 at 12:00
  • $\begingroup$ @Anuran Chowdhury Yes it is correct. See my edited answer. $\endgroup$ – Robert Z Jul 14 '17 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.