# Combinatorial interpretation of identity $\sum_{k=0}^m\binom{m}{k}\cdot \frac{(-1)^k}{n+k+1}=\frac{n!\cdot m!}{(n+m+1)!}$

I recently came across the identity

$$\sum_{k=0}^m\dbinom{m}{k}\cdot \frac{(-1)^k}{n+k+1}=\dfrac{n!\cdot m!}{(n+m+1)!},$$

while working on evaluating

$$\int_0^1 x^n(1-x)^m\, dx.$$

I ended up showing that both sides of the identity were equal to this integral, but I was wondering if there was a way to show directly (either by manipulation or some combinatorial argument) that one was equal to the other. Any help is much appreciated.

• This identity appeared at this MSE link. Commented Sep 4, 2015 at 20:35

One possible combinatorial explanation results from multiplying everything by $n+1$: $$\sum_{k=0}^m \binom{m}{k} (-1)^k \frac{n+1}{n+1+k} = \frac{1}{\binom{n+m+1}{m}}.$$ On the left-hand side we have an inclusion-exclusion formula, which counts the probability that none of the bad events $B_1,\ldots,B_m$ happen; the probability that $k$ specific bad events happen is $(n+1)/(n+1+k)$.

One possible experiment which can underlie this identity is the one in which you sample $m$ balls with replacement out of $n+2$ "colors", with uniform distribution over the $\binom{n+m+1}{m}$ different choices. The bad event $B_i$ is that ball $i$ doesn't get color $1$, say. The probability that none of the bad events happen is exactly $1/\binom{n+m+1}{m}$. Each single balls is chosen uniformly, so the probability of $B_i$ is indeed $(n+1)/(n+2)$. I conjecture that the probability of the conjunction of any $k$ bad events is $(n+1)/(n+1+k)$, which implies your identity.

Induction and Pascal's Rule \begin{align} \sum_k(-1)^k\binom{m}{k}\frac1{j\binom{n+k+j}{j}} &=\sum_k(-1)^k\left[\binom{m-1}{k}+\binom{m-1}{k-1}\right]\frac1{j\binom{n+k+j}{j}}\tag1\\ &=\sum_k(-1)^k\binom{m-1}{k}\left[\frac1{j\binom{n+k+j}{j}}-\frac1{j\binom{n+k+j+1}{j}}\right]\tag2\\ &=\sum_k(-1)^k\binom{m-1}{k}\frac1{(j+1)\binom{n+k+j+1}{j+1}}\tag3\\ &=\sum_k(-1)^k\binom{m-m}{k}\frac1{(j+m)\binom{n+k+j+m}{j+m}}\tag4\\[3pt] &=\frac1{(j+m)\binom{n+j+m}{j+m}}\tag5 \end{align} Explanation:
$$(1)$$: Pascal's Rule
$$(2)$$: distribute the sum
$$\phantom{\text{(2):}}$$ substitute $$k\mapsto k+1$$ in the right-hand sum
$$\phantom{\text{(2):}}$$ collect the sums
$$(3)$$: expand into factorials, subtract, and collect
$$\phantom{\text{(3):}}$$ note that $$m$$ has been decreased and $$j$$ has been increased
$$(4)$$: repeat the previous process $$m$$ times
$$(5)$$: only the $$k=0$$ term survives

Set $$j=1$$ and we get $$\sum_k(-1)^k\binom{m}{k}\frac1{n+k+1}=\frac{n!\,m!}{(n+m+1)!}\tag6$$

Partial Fractions

Heaviside Method for Partial Fractions guarantees that we can write $$\frac{n!\,m!}{(n+m+1)!}=\frac{m!}{(n+1)(n+2)\cdots(n+m+1)}=\sum_{k=0}^m\frac{a_k}{n+k+1}\tag7$$ and compute $$a_k$$ by multiplying both sides by $$n+k+1$$ and evaluating at $$n=\color{#C00}{-k-1}$$: $$\require{cancel} \scriptsize\frac{m!}{\underbrace{(\color{#C00}{(-k-1)}+1)\cdots(\color{#C00}{(-k-1)}+k)}_{(-1)^kk!}\cancel{(\color{#C00}{(-k-1)}+k+1)}\underbrace{(\color{#C00}{(-k-1)}+k+2)\cdots(\color{#C00}{(-k-1)}+m+1)}_{(m-k)!}}=a_k\tag8$$ That is, $$a_k=(-1)^k\binom{m}{k}\tag9$$ Thus, $$(7)$$ and $$(9)$$ give $$(6)$$.