3
$\begingroup$

I am trying to solve a combinatorics problems where I need to compute a sum based on binomial coffecients:

$${\sum_k}{\frac{1}{k+1}}{99\choose k}{200\choose 120 - k} $$

The only pattern that I can see here is :

$${\sum_k}{99\choose k}{200\choose 120 - k} = {99 + 200\choose 120}$$

My guess has been that I need to incorporate the $${\frac{1}{k+1}}$$ in order to match the form:

$${\sum_k}{n\choose k}{m\choose l - k} = {m + n\choose l}$$

I have tried decomposing the binomial coefficients into their factorial form:

$${\sum_k}{\frac{1}{k+1}}{99\choose k}{200\choose 120 - k} $$ = $${\sum_k}{\frac{1}{k+1}}{\frac{99!}{k! * (99 - k)!}}{\frac{200!}{(120 - k)! * (200 - (120 - k))!}} $$

=

$${\sum_k}{\frac{99!}{(k + 1)! * (99 - k)!}}{\frac{200!}{(120 - k)! * (200 - (120 - k))!}} $$

I do not see any patterns here that can lead me to the correct answer. Any advice or direction would be appreciated! Please do not post a solution!

$\endgroup$
1
$\begingroup$

You may get rid of that $\frac{1}{1+k}$ in the following way: $$ \frac{1}{k+1}\binom{99}{k} = \frac{99!}{(k+1)!(99-k)!}=\frac{1}{100}\binom{100}{k+1} $$ then exploit a well-known convolution. You are essentially computing the coefficient of $x^{121}$ in the product between $(1+x)^{100}$ and $(1+x)^{200}$.

$\endgroup$
  • 1
    $\begingroup$ Thanks! I applied Vandermonde's convolution to the result, if anyone was interested. $\endgroup$ – jonnywalkerr Oct 1 '15 at 19:38
0
$\begingroup$

One more trick: $\frac{1}{k+1} = \int_{0}^{1} x^k dx$ to get rid of the fraction.

$\endgroup$

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.