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)!}$

Question

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.

Answer 1

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.

Answer 2

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