Saturday, February 18, 2017

summation - 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?


Answer



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$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...