Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Welcome to! 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 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


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


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


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.

share|cite|improve this answer
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.

share|cite|improve this answer
"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}.$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.