11
$\begingroup$

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

  • 0
    Yes - that will work!2012-05-09

3 Answers 3

8

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.

  • 0
    @user30946: One of all-time favorites.2012-05-09
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}.$

1

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.

  • 0
    "Introduce the integral representation" lol2015-06-23