Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
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

1 Answer 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


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

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.