proof that $1 = \sum\limits_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$

Solution 1:

Here's an integral-free computational proof.

$$\begin{align*} \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}&=\sum_{k=0}^n(-1)^k\binom{2n}n\binom{n}k\frac{n}{n+k}\\ &=\sum_{k=0}^n(-1)^k\frac{(2n)^{\underline{n+1}}}{k!(n-k)!(n+k)}\\ &=\sum_{k=0}^n(-1)^k\frac{(2n)^{\underline{n-k}}(n+k-1)^{\underline{k}}}{k!(n-k)!}\\ &=\sum_{k=0}^n(-1)^k\binom{2n}{n-k}\binom{n+k-1}k\\ &=\sum_{k=0}^n(-1)^k\binom{2n}{n-k}\binom{n+k-1}{n-1}\;. \end{align*}$$

Identity (5.24) in Graham, Knuth, & Patashnik, Concrete Mathematics, is

$$\sum_k(-1)^k\binom{\ell}{m+k}\binom{s+k}n=(-1)^{\ell+m}\binom{s-m}{n-\ell}$$

for integer $\ell\ge 0$ and integers $m$ and $n$. We almost have the special case

$$\sum_k(-1)^k\binom{\ell}{m+k}\binom{s+k}s=(-1)^{\ell+m}\binom{s-m}{s-\ell}\;,$$

with $\ell=2n$, $m=n$, $s=n-1$:

$$\sum_k(-1)^k\binom{2n}{n+k}\binom{n-1+k}{n-1}=(-1)^{3n}\binom{-1}{-1-n}=0\;.$$

The summation in the identity is over all integers $k$, so

$$\begin{align*}\sum_{k\ge 0}(-1)^k\binom{2n}{n+k}\binom{n-1+k}{n-1}&=\sum_{k<0}(-1)^{k+1}\binom{2n}{n+k}\binom{n-1+k}{n-1}\\ &=\sum_{k=1}^n(-1)^{k+1}\binom{2n}{n+k}\binom{n-1-k}{n-1}\\ &\stackrel{*}=\sum_{k=1}^n(-1)^{k+1}\binom{2n}{n+k}(-1)^{n-1}\binom{n-1-(n-1-k)-1}{n-1}\\ &=\sum_{k=1}^n(-1)^{n+k}\binom{2n}{n+k}\binom{k-1}{n-1}\\ &=(-1)^{2n}\binom{2n}{2n}\\ &=1\;, \end{align*}$$

where the starred step is by what GKP calls negating the upper index.

Solution 2:

You asked for a combinatorial proof. Given the fractions in the identity, perhaps a probabilistic proof makes more sense. In any case, here's a probabilistic proof of the reformulation of the identity $$ \sum_{k=0}^n \binom{n}{k} (-1)^k \frac{1}{n+k} = \frac{1}{n \binom{2n}{n}} = \frac{(n-1)! n!}{(2n)!}.$$

Question: Suppose you have $n-1$ numbered red balls, $n$ numbered blue balls, and 1 black ball in a jar. Suppose you draw the balls, one-by-one, from the jar without replacing them. What is the probability that you draw all the red balls, followed by the black ball, followed by the blue balls?

Answer 1: There are $(n-1)!$ ways to draw the red balls, times 1 way to draw the black ball, times $n!$ ways to draw the blue balls, out of $(2n)!$ total ways to draw the balls, for a probability of $$\frac{(n-1)! n!}{(2n)!}.$$

Answer 2: Use inclusion/exclusion. Let $B$ be the event that the black ball is drawn after all the red balls. Let $A_i$ be the event that the black ball is drawn before the blue ball numbered $i$. We want $P(B \cap \left( \cap_{i=1}^n A_i \right)$. The event consisting of $B$ and any particular $k$ of the $\bar{A}_i$'s is the event that the black ball comes after all the red balls and after $k$ specific blue balls. This event has probability $1/(n-1 + k + 1) = 1/(n+k)$. By the principle of inclusion/exclusion, then, the answer to the question is also $$ \sum_{k=0}^n \binom{n}{k} (-1)^k \frac{1}{n+k}.$$