a sum with binomial coefficients

Question

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.

Answer 1

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

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

Answer 2

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

Answer 3

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.