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

I'm looking for a proof of this identity:

$$1 = \sum_{k=0}^n (-1)^k { 2n \choose n,k,n-k } \frac{n}{n+k}$$

I'll take anything, but a combinatorial proof would be nice - all of the terms in the sum appear to be integers.

Update: Given J.M.'s reformulation, if we start with $$x^{n-1} (1-x)^n = \sum_{k=0}^n { n \choose k } (-1)^k x^{n+k-1}$$ and integrate both sides from 0 to 1 wrt $x$ we get: $$\int_0^1 x^{n-1} (1-x)^n dx = \sum_{k=0}^n { n \choose k } \frac{(-1)^k}{n+k}$$ and so it is sufficient to prove that the integral is $1/( n { 2n \choose n } )$.

My instinct tells me to try a trigonometric substitution ($x = \cos^2 u$?) to evaluate the integral - haven't worked out all the details, though. (Update: see leslie townes comment below.)

In any case, I would really like to find a combinatorial proof.

Update 2: Found this paper: Walking into an absolute sum and the sum I'm interested in is $P_n(1)$ where $P_n(x)$ is the polynomial defined by: $$P_0(x) = 1 \\ P_{n+1}(x) = x^2 [ P_n(x) - P_n(x-1) ] + x P_n(x-1)$$ From this definition it is clear that $P_n(0) = 0$ for $n > 0$ and so $P_n(1) = 1$.

-
Welcome to math.se! What have you tried? What do you know? Answering these types of questions can help us help you. – chris May 9 '12 at 3:53
Would $$1=n\binom{2n}{n}\sum_{k=0}^n \binom{n}{k}\frac{(-1)^k}{n+k}$$ be easier for you to prove? – J. M. May 9 '12 at 3:58
That's what I originally started with! I'll take another look... – user30946 May 9 '12 at 4:47
For evaluating the integral, considering the properties of the family of integrals in en.wikipedia.org/wiki/Beta_function may help. – leslie townes May 9 '12 at 5:22
Yes - that will work! – user30946 May 9 '12 at 6:02

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.

-
Ah Concrete Mathematics! Several years ago I loaned it out and never got it back. :-( – user30946 May 9 '12 at 6:30
@user30946: One of all-time favorites. – Brian M. Scott May 9 '12 at 6:31

Suppose we seek to evaluate $$\sum_{k=0}^n (-1)^k {2n\choose n,k,n-k}\frac{n}{n+k}.$$

First do the binomial simplification as already noted by Brian M. Scott.

We start with $$\frac{(2n)!}{n!\times k!\times (n-k)!} \frac{n}{n+k} \\ = \frac{(2n)!\times (n+k-1)!} {(n-1)!\times k!\times (n-k)!\times (n+k)!} \\ = {2n\choose n-k} {n+k-1\choose n-1}$$ which gives for the sum $$\sum_{k=0}^n (-1)^k {2n\choose n-k} {k+n-1\choose n-1}.$$

Introduce the integral representation $${2n\choose n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n-k+1}} \; dz.$$

Note that this integral is zero when $k\gt n$ so we may extend the range of the sum to infinity, getting $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \sum_{k=0}^\infty (-1)^k {k+n-1\choose n-1} z^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z^{n+1}} \frac{1}{(1+z)^n} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n}}{z^{n+1}} \; dz.$$

This evaluates to one by inspection, QED.

-
"Introduce the integral representation" lol – Shadock Jun 23 '15 at 2:06

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

-