# Find closed form of sum of fraction of binomial coefficients

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?

• 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? – Mostafa Ayaz Jan 13 at 20:38

Let

$$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*}