# a sum with binomial coefficients

Let integers $n,k$ satisfy $0 \le k \le n$. We desire proof that $${n\choose k} = \sum {n\choose a}(-1)^a\;{-k\choose b}(-1)^b\;{-(n-k)\choose c}(-1)^c \tag{*}$$ where the (finite) sum is over all ordered triples $(a,b,c)$ of nonnegative integers satisfying $$a\cdot n + b\cdot k + c\cdot(n-k) = k(n-k) \\ \text{(or equivalently}\quad \frac{a+b}{n-k} + \frac{a+c}{k} = 1 \quad).$$ Of course the binomial coefficient for a binomial to a negative power is $${-k\choose b} = \frac{(-k)(-k-1)(-k-2)\cdots(-k-b+1)}{b!} .$$

Now two of the terms in ($*$) are $(a,b,c)=(0,n-k,0)$ and $(a,b,c)=(0,0,k)$. Those two terms do, indeed, add to ${n\choose k}$. But then the problem becomes: show that the rest of the terms sum to zero.

Note
This arose from my attempt to solve integral of a "sin-omial" coefficients=binomial . It is the calculation of the residue at $w=0$ of rational function $$\frac{(w^n-w^{-n})^n}{(w^k-w^{-k})^k(w^{n-k}-w^{-(n-k)})^{n-k}w}$$ obtained by changing variables in the integral of that problem.

• Have you tried using a computer to find a WZ pair? en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_pair – Steve Huntsman Nov 3 '16 at 13:22
• you could try Christian Krattenthaler's mathematica package hyp.m, which would produce a human-readable proof, but a prerequisite is that the summation bounds are "natural", i.e., can be replaced by a sum over all triples $(a,b,c)$. – Martin Rubey Nov 3 '16 at 13:23
• can we use vandermonde identity? – vidyarthi Nov 3 '16 at 15:49
• @TimothyChow ... I will reveal that in due course. – Gerald Edgar Nov 5 '16 at 0:30
• @SteveHuntsman and Martin: I do not expect neither WZ nor hyp.m to work here because the the binomial coefficient sum is a red herring. The "constant-term" extraction is a way to go. In other words, it is better to say with the rational function shown (in the variable $w$) in the OP's question. – T. Amdeberhan Nov 5 '16 at 14:28

Ira told me this interesting constant term identity.

It is not hard to see that the problem is equivalent to showing the following constant term identity: $$\binom{n}{k} = \frac{(1-x^n)^n}{(1-x^k)^k (1-x^{n-k})^{n-k} x^{k(n-k)}} \Big|_{x^0},$$ where $0\le k \le n$. To obtain the given binomial sum identity, simply apply the binomial theorem and equate coefficients.

The proof replies on the following two key facts.

1. If we write $\displaystyle F(x)=\frac{(1-x^n)^n}{(1-x^k)^k (1-x^{n-k})^{n-k} x^{k(n-k)}}$ then $F(x^{-1})=F(x)$.

So the constant term can be regarded as an identity in $\mathbb{Q}((x))$ and also an identity in $\mathbb{Q}((x^{-1}))$.

1. $F(x)$ is invariant if we replace $k$ by $n-k$.

We will use partial fraction decomposition to obtain different formula of $F(x) \big|_{x^0}$ and deduce that the constant term is equal to $\binom{n}{k}$.

Firstly notice that it is hard to work directly using partial fraction decomposition of $F(x)$. We consider the partial faction of $F(x,t)$ with $F(x)=F(x,1)$ instead. $$F(x,t)=\frac{(1-t^2 x^n)^n}{(1-tx^k)^k (1-tx^{n-k})^{n-k} x^{k(n-k)}}$$ Now we have a unique partial fraction decomposition with respect to $x$ $$F(x,t) =C+ P_+(x)+P_-(x^{-1}) + \frac{N_1(x)}{(1-tx^k)^k} + \frac{N_2(x)}{(1-tx^{n-k})^{n-k}},$$ where $P_{\pm}(x)$ are polynomials with $P_{\pm}(0)=0$, $\deg N_1(x)<k^2$, $\deg N_2(x)<(n-k)^2$, and every term may contain the slack variable $t$ which will be set equal to $1$, then by working in $\mathbb{Q}((x))$ and $\mathbb{Q}((x^{-1}))$, we get \begin{align*} F(x) \big|_{x^0} &=C\big|_{t=1}, \\ F(x) \big|_{x^0} &=(C+ N_1(0)+N_2(0)) \big|_{t=1}. \end{align*} Consequently $(N_1(0)+N_2(0))\big|_{t=1}=0$.

Next we split $1-t^2x^n$ as $(1-tx^k)+tx^{k}(1-tx^{n-k})$ and apply the binomial theorem. \begin{align*} F(x,t)&=\frac{(1-t^2x^n)^n}{(1-tx^k)^k (1-tx^{n-k})^{n-k} x^{k(n-k)}} \\ &= \frac{\sum_{i=0}^n \binom{n}{i}(1-tx^k)^i (tx^k(1-tx^{n-k}))^{n-i} }{(1-tx^k)^k (1-tx^{n-k})^{n-k} x^{k(n-k)}} \\ &= \binom{n}{k}t^k + \sum_{i=0}^{k-1} \binom{n}{i} \frac{t^{n-i} x^{k(k-i)} (1-tx^{n-k})^{k-i}}{(1-tx^k)^{k-i} } + \sum_{i=k+1}^{n} \binom{n}{i} \frac{t^{n-i} x^{-k(i-k)} (1-tx^k)^{i-k}}{(1-tx^{n-k})^{i-k} } \end{align*} If we work in $\mathbb{Q}((x))$, we get $F(x,1)\big|_{x^0} = \binom{n}{k} + N_2(0)\big|_{t=1},$ since the constant term of the middle term is clearly $0$.

A similar argument shows that $F(x)\big|_{x^0} = \binom{n}{k} + N_1(0)\big|_{t=1}.$ This should also follows from the observation that $F(x,t)$ is invariant under replacing $k$ by $n-k$. Thus we obtain $$2 F(x,1)\big|_{x^0} = 2 \binom{n}{k} + N_1(0)\big|_{t=1}+N_2(0)\big|_{t=1}= 2 \binom{n}{k}.$$ This concludes that $F(x)\big|_{x^0}=\binom{n}{k}.$

• Ira = Ira Gessel, presumably? – Sam Hopkins Nov 4 '16 at 18:35
• So it seems that reason for the partial fractions fails if $k=n-k$. But that case is even easier. – Gerald Edgar Nov 4 '16 at 21:33
• Yes. The case $k=n-k$ has to be treated separately. Ira Gessel found a gap in the argument: for $N_2(0)\big|_{t=1}$ to be well-defined we need to show $t=1$ is not a pole. For this we change this to limit. The formula $F(x)\big|_{x^0} = \binom{n}{k} + \lim_{t=1} N_2(0)$ implies $t=1$ can not be a pole of $N_2(0)$. – Guoce Xin Nov 5 '16 at 20:44
• I believe this proof is simply wrong. Should I edit it? (I don't know the etiquette here.) – Alex Selby Nov 20 '16 at 2:20
• That is because the third term is a proper rational function, i.e., the degree in the numerator is greater than the degree in the demominator. If you convert it to partial fraction, you will have $D(x^{-1},t) + N'_2(t,x)/(1-tx^{n-k})^{n-k}$, whose constant term is $N'_2(t,0)$. For the second term if you convert it to partial fraction decomposition, you have $P(x,t)+ N'_1(t,x)/(1-tx^k)^k$, whose constant term is known to be $0$ in advance. By the uniqueness of partial fraction decomposition, $N_2(t,x)=N_2'(t,x)$. – Guoce Xin Dec 4 '16 at 5:00

If we set $b' = a+b$ and $c' = a+c$, then your sum can be explicitly evaluated for $b'\in\{1,\ldots,n-k\}$ and $c'\in\{1,\ldots,k\}$ fixed (but otherwise no condition on $b'$,$c'$). Indeed, as Mathematica is happy to tell us, we have

\begin{eqnarray}\sum_{a=0}^{\min(b',c')}(-1)^a\binom{n}{a}(-1)^{b'}\binom{-k}{b'-a}(-1)^{c'}\binom{-(n-k)}{c'-a} \tag{1}\\ = (-1)^{b'+c'}\binom{-k}{b'}\binom{k-n}{c'}{_3F_2}\left(\begin{matrix}-n & -b' &-c'\\ &1-b'-k& 1-c'+k-n\end{matrix};1\right). \end{eqnarray}

Using Sheppard's identity (W. F. Sheppard, "Summation of the Coefficients of Some Terminating Hypergeometric Series", Proc. London Math. Soc. (1912) s2-10 (1): 469-478) equation (16) the hypergeometric function can be simplified to

\begin{eqnarray}&&{_3F_2}\left(\begin{matrix}-n & -b' &-c'\\ &1-b'-k& 1-c'+k-n\end{matrix};1\right) \\&&\quad= -\frac{b' k + c'(n-k)-k(n-k)}{(n-k)(b'-c'+k)}\cdot \frac{(c'-k)_{c'}(b'+k-n)_{c'}}{(c'-b'-k)_{c'}(k-n)_{c'}}, \end{eqnarray} in terms of the Pochhammer symbol $(x)_n = x (x-1)\cdots (x-n+1)$. Hence, the sum (1) vanishes when $b' k + c'(n-k)-k(n-k) = 0$.

Therefore the only contribution to $(*)$ can come from $b'=0$ or $c'=0$, i.e. $(a,b,c) = (0,n-k,0)$ or $(a,b,c) = (0,0,k)$.

• Where the argument of vanishing of (1) fails for $b'=0$ or $c'=0$? – Max Alekseyev Nov 4 '16 at 16:27
• I've corrected the simplified formula following the Sheppard (1912) reference. It can be now seen that it fails for $(b',c')=(0,k)$ giving $0$ in the denominator. But what's about $(b',c')=(n-k,0)$ ? – Max Alekseyev Nov 4 '16 at 18:44
• Maybe I should have been a bit clearer how I got my formula from Sheppard's: I took $(n,\beta,\theta,\phi) = (c',-n,1-b'-k,1-c'+k-n)$. Then none of the Pochhammer symbols vanish, except one in the denominator when $(b',c')=(0,k)$. On the other hand, the factor $b'-c'+k-n$ vanishes only when $(b',c')=(n-k,0)$. If you agree I'll revert to my formula. – Timothy Budd Nov 4 '16 at 21:24
• OK. But for Pochhammer symbol, it's better keep falling not raising factorial. – Max Alekseyev Nov 4 '16 at 22:12
• Do I understand correctly that this proves the conjecture, modulo the proof of (1), which is "only" provided by Mathematica? – Wolfgang Nov 9 '16 at 12:56

This is an elementary/self-contained proof based on manipulation of binomials.

Let $l=n-k$ and $g=\gcd(n,k)=\gcd(k,l)$.

The condition $an+bk+cl=kl$ (where $a$, $b$, and $c$ are as in the original problem description) is equivalent to $(a+c)n=k(l+c-b)$, which means $k/g\mid a+c$, so $a+c=tk/g$, $a+b=l(1-t/g)$, and the only possible values of $t$ are $0,1,\ldots,g$. $t=0$ and $t=g$ correspond to $(a,b,c)=(0,l,0)$ and $(a,b,c)=(0,0,k)$ respectively, which provide ${n\choose k}$ as mentioned in the problem description (by an easy binomial sum).

The problem is to show that $t=1,\ldots,g-1$ contribute zero in total to the sum (obvious if $n$ and $k$ are coprime). Helpfully it turns out that the contributions from each value of $t$ are separately zero, not just in aggregate, and the WZ method can be applied to each $t$ as follows.

To make the notation slightly prettier, define $\tau=t/g$ and $\tau'=1-t/g$. (There is then a symmetry $k\leftrightarrow l$, $\tau\leftrightarrow\tau'$.) $\tau$ and $\tau'$ will only ever occur multiplied by $k$, $l$ or $n$, so everything is an integer.

What needs to be proved is, for fixed $t$ between $1$ and $g-1$, $$\sum_{a=0}^{\min(k\tau,l\tau')} (-1)^a {n\choose a}{-k\choose l\tau'-a}{-l\choose k\tau-a}=0.$$

This is established by the explicit sum, valid for $0<\tau<1$: $$\sum_{a=0}^{r-1} (-1)^a {n\choose a}{-k\choose l\tau'-a}{-l\choose k\tau-a}= (-1)^{r+1} {n\choose r}{-k\choose l\tau'-r}{-l\choose k\tau-r} \frac{r(l+k\tau-r)(k+l\tau'-r)}{kln\tau\tau'},$$ which vanishes for $r>\min(k\tau,l\tau')$. It is routine to check that the delta of the RHS is the LHS.