18
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Have you tried using a computer to find a WZ pair? en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_pair $\endgroup$ – Steve Huntsman Nov 3 '16 at 13:22
  • $\begingroup$ 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)$. $\endgroup$ – Martin Rubey Nov 3 '16 at 13:23
  • $\begingroup$ can we use vandermonde identity? $\endgroup$ – vidyarthi Nov 3 '16 at 15:49
  • 1
    $\begingroup$ @TimothyChow ... I will reveal that in due course. $\endgroup$ – Gerald Edgar Nov 5 '16 at 0:30
  • 2
    $\begingroup$ @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. $\endgroup$ – T. Amdeberhan Nov 5 '16 at 14:28
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ira = Ira Gessel, presumably? $\endgroup$ – Sam Hopkins Nov 4 '16 at 18:35
  • 1
    $\begingroup$ So it seems that reason for the partial fractions fails if $k=n-k$. But that case is even easier. $\endgroup$ – Gerald Edgar Nov 4 '16 at 21:33
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Guoce Xin Nov 5 '16 at 20:44
  • 1
    $\begingroup$ I believe this proof is simply wrong. Should I edit it? (I don't know the etiquette here.) $\endgroup$ – Alex Selby Nov 20 '16 at 2:20
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Guoce Xin Dec 4 '16 at 5:00
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Where the argument of vanishing of (1) fails for $b'=0$ or $c'=0$? $\endgroup$ – Max Alekseyev Nov 4 '16 at 16:27
  • $\begingroup$ 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)$ ? $\endgroup$ – Max Alekseyev Nov 4 '16 at 18:44
  • $\begingroup$ 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. $\endgroup$ – Timothy Budd Nov 4 '16 at 21:24
  • $\begingroup$ OK. But for Pochhammer symbol, it's better keep falling not raising factorial. $\endgroup$ – Max Alekseyev Nov 4 '16 at 22:12
  • $\begingroup$ Do I understand correctly that this proves the conjecture, modulo the proof of (1), which is "only" provided by Mathematica? $\endgroup$ – Wolfgang Nov 9 '16 at 12:56
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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