can somebody give me a hint for this exercise, where I have to find the specific closed form?

$\sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}, m,n\in\mathbb{N}$ and $m\leq n$

What I have done so far:

$\sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}} = \sum_{k=0}^m \frac{\frac{m!}{(m-k)!\cdot k!}}{\frac{n!}{(n-k)!\cdot k!}} = \sum_{k=0}^m \frac{m!}{n!}\cdot \frac{(n-k)!}{(m-k)!} = \frac{m!}{n!}\cdot \sum_{k=0}^m \frac{(n-k)!}{(m-k)!}$

Look at example 1: $n=8, m=5$

$\frac{5!}{8!}\cdot(\frac{8!}{5!} + \frac{7!}{4!} +\frac{6!}{3!} +\frac{5!}{2!} + \frac{4!}{1!} +\frac{3!}{0!}) = \\\frac{5!}{8!} \cdot (8\cdot7\cdot6+7\cdot6\cdot5+6\cdot5\cdot4+5\cdot4\cdot3+4\cdot3\cdot2+3\cdot2\cdot1) = \\ \frac{5!}{8!} \cdot (336+210+120+60+24+6) = \frac{5!}{8!}\cdot 756 = 2.25$

I can't find a pattern.

Edit 1: Maybe there is an approach with recursion.

Edit 2: Okay I found the solution.

$\sum_{k=0}^m \frac{m!}{n!}\cdot \sum_{k=0}^m \frac{(n-k)!}{(m-k)!}= \frac{m!}{n!}\cdot\frac{1}{4}\cdot t\cdot(t+1)\cdot(t+2)\cdot(t+3)$ with $t=(n-m)!$

Edit 3: This formula works well for example 1, but fails for example 2: $n=9, m=3$

$\frac{3!}{9!}\cdot(\frac{9!}{3!} + \frac{8!}{2!} +\frac{7!}{1!} +\frac{6!}{0!}) = \\\frac{3!}{9!} \cdot (9\cdot8\cdot7\cdot6\cdot5\cdot4+8\cdot7\cdot6\cdot5\cdot4\cdot3+7\cdot6\cdot5\cdot4\cdot3\cdot2+6\cdot5\cdot4\cdot3\cdot2\cdot1) = \\ \frac{3!}{9!} \cdot (60480+20160+5040+720) = \frac{3!}{9!}\cdot 86400 = 1.428$

So I have still no general solution. Can someone help?

  • $\begingroup$ Hope the following combinatorial problem help you: given $n$ marbles $m$ of whom are black and the rest are red, what's the probability of choosing at most $m$ marbles all of which being black? $\endgroup$ – Mostafa Ayaz Jan 13 at 20:38


$$S(m,n):=\sum_{k=0}^m \frac{\binom{m}{k}}{\binom{n}{k}}$$

We are going to prove: $$S(m,n)=\frac{n+1}{n+1-m}.\tag{1}$$

Obviously (1) is valid for $m=0$ and arbitray $n\ge 0$. Further, if (1) is valid for $(m-1,n-1)$ it is valid for $(m,n)$ as well: $$ S(m,n):=1+\sum_{k=1}^m \frac{\frac mk\binom{m-1}{k-1}}{\frac nk\binom{n-1}{k-1}} =1+\frac{m}{n} S(m-1,n-1)\\ \stackrel{I.H.}{=}1+\frac{m}{n}\frac{n}{n+1-m}=\frac{n+1}{n+1-m}. $$

Thus by induction (1) is valid for arbitrary $0\le m \le n$.


With $m\le n$ we have the sum

$$\sum_{k=0}^m {m\choose k} {n\choose k}^{-1} = \sum_{k=0}^m \frac{m!}{(m-k)! k!} \frac{k! (n-k)!}{n!} \\ = \frac{m!}{n!} \sum_{k=0}^m \frac{(n-k)!}{(m-k)!} = {n\choose m}^{-1} \sum_{k=0}^m {n-k\choose m-k} \\ = {n\choose m}^{-1} \sum_{k=0}^m [z^{m-k}] (1+z)^{n-k} = {n\choose m}^{-1} [z^m] (1+z)^n \sum_{k=0}^m z^k (1+z)^{-k}.$$

We may extend $k$ beyond $m$ due to the $z^k$ term and the coefficient extractor $[z^m]$ in front, getting

$${n\choose m}^{-1} [z^m] (1+z)^n \sum_{k\ge 0} z^k (1+z)^{-k} = {n\choose m}^{-1} [z^m] (1+z)^n \frac{1}{1-z/(1+z)} \\ = {n\choose m}^{-1} [z^m] (1+z)^{n+1} = {n\choose m}^{-1} {n+1\choose m} = \frac{n+1}{n+1-m}.$$


Hint: Use the beta function \begin{align*} \binom{n}{k}^{-1}=(n+1)\int_0^1(1-x)^kx^{n-k}\,dx \end{align*}


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.