20
$\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$
7
  • 1
    $\begingroup$ Have you tried using a computer to find a WZ pair? en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_pair $\endgroup$ Nov 3, 2016 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$ Nov 3, 2016 at 13:23
  • $\begingroup$ can we use vandermonde identity? $\endgroup$
    – vidyarthi
    Nov 3, 2016 at 15:49
  • 1
    $\begingroup$ @TimothyChow ... I will reveal that in due course. $\endgroup$ Nov 5, 2016 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$ Nov 5, 2016 at 14:28

3 Answers 3

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$
8
  • $\begingroup$ Ira = Ira Gessel, presumably? $\endgroup$ Nov 4, 2016 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$ Nov 4, 2016 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, 2016 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, 2016 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, 2016 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$
6
  • $\begingroup$ Where the argument of vanishing of (1) fails for $b'=0$ or $c'=0$? $\endgroup$ Nov 4, 2016 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$ Nov 4, 2016 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$ Nov 4, 2016 at 21:24
  • $\begingroup$ OK. But for Pochhammer symbol, it's better keep falling not raising factorial. $\endgroup$ Nov 4, 2016 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, 2016 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 and acknowledge you have read our privacy policy.

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