Binomial-coefficients if, k, m, n natural numbers and k \leq n the result of

Question

If $k, m, n$, are natural numbers and $k \leq n$ What is:

$$\sum_{r=0}^{m}\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}$$

Answer 1

$$\Large\begin{align} \sum_{r=0}^{m}\frac{\color{green}k\binom{m}{r}\color{green}{\binom{n}{k}}}{\color{blue}{(r+k)\binom{m+n}{r+k}}} &=\frac{\color{green}{n } }{\color{blue}{m+n}} \sum_{r=0}^{m}\frac{\binom mr\color{green}{\binom {n-1} {k-1}}}{\color{blue}{\binom {m+n-1}{r+k-1}}}\\\\ &=\frac{n}{m+n} \cdot \frac{m+n}{n}\\\\ &=1\qquad \blacksquare \end{align}$$

---

NB: the proof above uses the identity $$\sum_{r=0}^m \large\frac{\binom mr\binom ab}{\binom {m+a}{r+b}}=\frac{m+a+1}{a+1}$$ where $a=n-1, b=k-1$. The derivation of this is given below.

Note that $$\begin{align} \binom{m+a}m\binom m{r+b}&=\color{purple}{\binom {m+a}{r+b}}\binom {m+a-r-b}{m-r-b}\\\\ \Rightarrow \color{purple}{\binom {m+a}{r+b}}&=\large\frac{\binom{m+a}m\binom m{r+b}}{\binom {m+a-r-b}{m-r-b}} =\color{purple}{\frac{\binom{m+a}a\binom m{r+b}}{\binom {m+a-r-b}a}}\\\\ \sum_{r=0}^{m}\large\frac{\binom mr\binom ab}{\color{purple}{\binom {m+a}{r+b}}} &=\sum_{r=0}^{m}\binom mr \binom ab\large\color{purple}{\frac{\binom {m+a-r-b}a}{\binom{m+a}a\binom m{r+b}}}\\ &=\binom {m+a}a^{-1}\sum_{r=0}^m\large\frac{\binom m{m-r}\color{orange}{\binom {m+a-r-b}{a}\binom a{a-b}}}{\binom m{r+b}}\\ &=\binom {m+a}a^{-1}\sum_{r=0}^m\large\frac{\binom m{m-r}\color{orange}{\binom {m+a-r-b}{a-b}\binom {m-r}b}}{\binom m{r+b}}\\ &=\binom {m+a}a^{-1}\sum_{r=0}^m\large\frac{\color{red}{\binom m{m-r}\binom {m-r}{m-r-b}}\binom {m+a-r-b}{a-b}}{\binom m{r+b}}\\ &=\binom {m+a}a^{-1}\sum_{r=0}^m\large\frac{\color{red}{\binom m{r+b}\binom {r+b}{b}}\binom {m+a-r-b}{a-b}}{\binom m{r+b}}\\ &=\binom {m+a}a^{-1}\sum_{r=0}^m\binom {b+r}{b}\binom {m+a-b-r}{a-b}\\ &=\binom {m+a}a^{-1}\binom {b+(m+a-b)+1}{b-b+(m+a-b)-(a-b)}\quad \text{(see ** below)}\\ &=\binom {m+a}a^{-1}\binom {m+a+1}m\\ &=\binom {m+a}a^{-1}\binom {m+a+1}{a+1}\\ &=\frac{m+a+1}{a+1}\qquad \blacksquare \end{align}$$

---

** makes use of the summation identity $$\sum_{r=0}^n \binom {A+r}B \binom {C-r}D=\binom {A+C+1}{A-B+C-D}$$ where $A=b, B=b, C=m+a-b, D=a-b$.

The identity can be proven as follows: $$\begin{align} \sum_{r=0}^n \binom {A+r}B \binom {C-r}D &=\sum_{r=0}^n \binom {A+r}{A+r-B}\binom {C-r}{C-r-D}\\ &=\sum_{r=0}^n (-1)^{A+r-B+C-r-D}\binom {-B-1}{A+r-B}\binom {-D-1}{C-r-D}\\ &=(-1)^{A-B+C-D}\binom{-B-D-2}{A-B+C-D}\quad \text{(using Vandermonde)}\\ &=(-1)^{2(A-B+C-D)}\binom{A+C+1}{A-B+C-D}\\ &=\binom{A+C+1}{A-B+C-D}\qquad \blacksquare\\ \end{align}$$

Answer 2

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

Continue making calculations.

Answer 3

Here's a slightly different answer to this nice question.

We observe: \begin{align*} \sum_{r=0}^{m}&\frac{k\binom{m}{r}\binom{n}{k}}{(r+k)\binom{m+n}{r+k}}\tag{1}\\ &=\sum_{r=0}^{m}\frac{m!}{r!(m-r)!}\frac{n!}{(k-1)!(n-k)!}\frac{(r+k-1)!(m+n-r-k)!}{(m+n)!}\tag{2}\\ &=\frac{m!n!}{(m+n)!}\sum_{r=0}^{m}\frac{(r+k-1)!}{r!(k-1)!}\frac{(m+n-r-k)!}{(m-r)!(n-k)!}\tag{3}\\ &=\binom{m+n}{m}^{-1}\sum_{r=0}^{m}\binom{r+k-1}{r}\binom{m-r+n-k}{m-r}\tag{4}\\ &=\binom{m+n}{m}^{-1}\sum_{r=0}^{m}\binom{-k}{r}(-1)^r\binom{-(n-k+1)}{m-r}(-1)^{m-r}\tag{5}\\ &=\binom{m+n}{m}^{-1}(-1)^m\binom{-(n+1)}{m}\tag{6}\\ &=\binom{m+n}{m}^{-1}\binom{m+n}{m}\tag{7}\\ &=1\\ \end{align*}

Comment:

• (2) In order to get a better overview we write all factorials explicitely and cancel the factors $k$ and $r+k$.

• (3) We factor out some factorials which do not depend on the index $r$ and we reorder the factorials since we want to write them as binomial coefficients to simplify further calculations.

• (4) Just a rewrite of (3) with the help of binomial coefficients. Observe that (4) and (1) look quite different although they are equal.

So, here we have a nice example underpinning the following remark by D.E. Knuth in section 5.5 Hypergeometric functions in Concrete Mathematics:

Binomial coefficients are like chameleons, changing their appearance easily.

• (5) We apply the following identity twice (see e.g. Vol 1, (1.6) in H.W. Goulds Table of binomial identities)

\begin{align*} \binom{-k}{r}=\binom{k+r-1}{k}(-1)^k\tag{8} \end{align*}

• (6) We use the Vandermonde identity

\begin{align*} \sum_{r}\binom{a}{r}\binom{b}{m-r}=\binom{a+b}{m}\qquad\qquad a,b\in \mathbb{R},m\in \mathbb{Z}\tag{9} \end{align*}

• (7) Here we use again identity (8)

Summary: The essence of this calculation is finding a convenient representation of the Vandermonde identity. (1) is a more or less complicated representation of it with the binomial coefficient of the RHS of (9) as reciprocal factor on the LHS.

---

A combinatorial interpretation of (1) is essentially that for the Vandermonde identity (9). We could argue e.g. in terms of lattice pathes on a rectangular grid:

We consider pathes containing only $(1,0)$-steps in $x$-direction and $(0,1)$-steps in $y$-direction. The expression

$$\binom{a+b}{m}$$

gives the number of all pathes of length $a+b$ from $(0,0)$ to $(m,a+b-m)$ containing exactly $m$ $(1,0)$ steps in $x$-direction. The sum

$$\sum_{r}\binom{a}{r}\binom{b}{m-r}$$

partitions these pathes in those of length $a$ with exactly $r$ $(0,1)$-steps in $x$-direction times the number of pathes of length $b$ with exactly $m-r$ $(0,1)$-steps in $x$-direction.