11
$\begingroup$

In my work, I was led to the following identity. I would be grateful if someone could provide an easy proof.

Suppose $n, d, k \in \mathbb{Z}$, and $d \geq 0$.

$$ \sum_{j = 0}^d (-1)^{d-j} \cdot \binom{d}{k} \cdot \binom{n-j-1}{n-d-1} \cdot \binom{n-d}{j-k} = \left\{ \begin{array}{ll} 0 & : d \neq k\\ 0 & : n < 0\\ 1 & : 0 \leq n \leq d\\ 2 & : d < n \end{array} \right. $$

I've been to the wikipedia page on binomial coefficients, looking for useful identities to apply. https://en.wikipedia.org/wiki/Binomial_coefficient

Many well-known identities seem applicable, but I don't know how to handle the way $j$ appears once in the top of one of the binomial coefficients, and once in the bottom. The identity

$$ \sum_{k=q}^n \binom{n}{k} \binom{k}{q} = 2^{n-q}\binom{n}{q} $$

has the moving variable in both places, but I do not see how to use this.

What I'm trying to avoid is proof by induction. The context is, I need this identity for an example in a paper. I don't want to get hung up on the example, but I'd like to include a full proof.

$\endgroup$
  • $\begingroup$ There is a $\dbinom{d}{k}$ in the sum that does not depend on $j$? $\endgroup$ – darij grinberg Jul 31 '15 at 20:37
  • 1
    $\begingroup$ My suspicion on the proof is that the first step is rewriting the $\dbinom{n-j-1}{n-d-1}$ as $\dbinom{n-j-1}{d-j}$ (by the symmetry of the Pascal's triangle) and then using upper negation on this term (which removes the $\left(-1\right)^{d-j}$). This should yield an instance of Vandermonde convolution. However, the use of symmetry requires $n-j-1 \geq 0$, which I am not sure how to guarantee; probably this requires studying the other two binomial terms. If the OP clearly explains what set $d$ and $k$ live in, this will become a lot more doable. $\endgroup$ – darij grinberg Jul 31 '15 at 22:03
  • 1
    $\begingroup$ @MorganRodgers The sum is usually zero, so being a multiple of \binom{d}{k} is no problem. The only time when the sum is nonzero is when d=k, and so the sum must be a multiple of 1; once again, no problem. $\endgroup$ – John Wiltshire-Gordon Jul 31 '15 at 22:04
  • 1
    $\begingroup$ What is the convention for $d = k = -1,\ 0 \le n$? Most conventions interpret sums over $j=0$ to $-1$ to be 0, where your identity produces 2 instead. $\endgroup$ – will Aug 1 '15 at 4:46
  • 1
    $\begingroup$ @darijgrinberg's suggestion is carried out here, with $l\rightarrow n-1$, $m\rightarrow n-d-1$, $s\rightarrow n-d$, $n\rightarrow k$. $\endgroup$ – joriki Aug 1 '15 at 16:14
4
+100
$\begingroup$

Calculation with small values of $n,d,k\geq 0$ shows the following is valid

\begin{align*} \sum_{j=0}^{d}(-1)^{d-j}\binom{d}{k}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k} = \begin{cases} 1&\qquad 0\leq k=d<n\\ 0&\qquad \text{otherwise} \end{cases} \tag{1} \end{align*}

Note: It's easy to prove the special case $k=d<n$. In order to show that the expression is zero otherwise we use techniques known as formal residual calculus for power series. They are based upon Cauchys residue theorem and were introduced by G.P. Egorychev (Integral Representation and the Computation of Combinatorial Sums) to compute binomial identies.

We start with the easy one

Case: $0\leq k=d<n$

If $k=d$ we obtain

\begin{align*} \sum_{j=0}^{d}&(-1)^{d-j}\binom{d}{k}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k}\tag{2}\\ &=\sum_{j=k}^{d}(-1)^{d-j}\binom{d}{k}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k}\\ &=(-1)^{d-d}\binom{d}{d}\binom{n-d-1}{n-d-1}\binom{n-d}{0}\\ &=1 \end{align*}

This proves the first part of (1).

Recall that a binomial coefficient $\binom{n}{k}$ is zero if $k<0$ or $n<k$. We observe in (2) the the index $j$ of the rightmost binomial coefficient $\binom{n-d}{j-k}$has to be greater or equal $k$ otherwise the summand contributes zero. So, the lower bound of the index $j$ is $k$.

We also note that the binomial coefficient $\binom{n-d-1}{n-d-1}$ is equal to $1$ only in the case $n-d-1\geq 0$ which means $d$ less than $n$ and the easy part of (1) is shown.

We also see that $\binom{d}{k}$ is zero if $d$ is less than $k$. So, the only case which remains is

Case: $0\leq k<d$

We use the residue notation and write e.g. \begin{align*} \mathop{res}_z\frac{(1+z)^{n}}{z^{k+1}}=\frac{1}{2\pi i}\oint_{|z|=1}\frac{(1+z)^{n}}{z^{k+1}}\mathop{dz}\tag{3} =[z^k](1+z)^n=\binom{n}{k} \end{align*}

In fact we will use only two aspects of this theory:

Let $A(z)=\sum_{j=0}^{\infty}a_jz^j$ be a formal power series, then

  • Write the binomial coeffients as residuals of corresponding formal power series

\begin{align*} \mathop{res}_{z}\frac{A(z)}{z^{j+1}}=a_j\tag{4} \end{align*}

  • Apply the substitution rule for formal power series:

\begin{align*} A(z)=\sum_{j=0}^{\infty}a_jz^{j}=\sum_{j=0}^{\infty}z^j\mathop{res}_{w}\frac{A(w)}{w^{j+1}}\tag{5} \end{align*}

\begin{align*} \binom{d}{k}\sum_{j=k}^{d}&(-1)^{d-j}\binom{n-j-1}{n-d-1}\binom{n-d}{j-k}\tag{6}\\ &=\binom{d}{k}\sum_{j=0}^{\infty}(-1)^{d-j}\mathop{res}_{z}\frac{(1+z)^{n-j-1}}{z^{n-d}} \mathop{res}_{u}\frac{(1+u)^{n-d}}{u^{j-k+1}}\tag{7}\\ &=(-1)^d\binom{d}{k}\mathop{res}_{z}\frac{(1+z)^{n-1}}{z^{n-d}} \sum_{j=0}^{\infty}\left(\frac{-1}{1+z}\right)^j \mathop{res}_u\frac{(1+u)^{n-d}u^k}{u^{j+1}}\tag{8}\\ &=(-1)^d\binom{d}{k}\mathop{res}_{z}\frac{(1+z)^{n-1}}{z^{n-d}} \left(1-\frac{1}{1+z}\right)^{n-d}\left(\frac{-1}{1+z}\right)^k\tag{9}\\ &=(-1)^{d+k}\binom{d}{k}\mathop{res}_{z}(1+z)^{d-k-1}\\ &=(-1)^{d+k}\binom{d}{k}[z^{-1}](1+z)^{d-k-1}\tag{10}\\ &=0 \end{align*}

Since $(1+z)^{d-k-1}$ has not a non-zero power of $z^{-1}$, the expression (10) is zero. This proves the second part of (1)

Comment:

  • In (7) we extend the upper limit of the sum without changing the value since we are only adding zeroes and we rewrite the binomial coefficients using residues according to (3) and (4)

  • In (8) we do some rearrangements to prepare for the substitution rule

  • In (9) we apply the substitution rule according to (5)

$\endgroup$
  • $\begingroup$ @JohnWiltshire-Gordon:Thanks a lot for accepting my answer and granting the bounty. Best regards, $\endgroup$ – Markus Scheuer Aug 2 '15 at 5:55
5
$\begingroup$

Substitute $r=d-j$ and use upper negation followed by Vandermonde's Identity: $$\require{cancel}\begin{align}\sum_{j=0}^d(-1)^{d-j}\binom{d}{k} \binom{n-j-1}{n-d-1} \binom{n-d}{j-k} &=\binom dk \sum_{r=0}^d(-1)^r\color{blue}{\binom{n-d-1+r}{n-d-1}}\binom{n-d}{d-k-r}\\ &=\binom dk \sum_{r=0}^d(-1)^r\color{blue}{\binom{n-d-1+r}r}\binom{n-d}{d-k-r}\\ &=\binom dk \sum_{r=0}^d(-1)^r\color{blue}{\binom{d-n}r(-1)^r}\binom{n-d}{d-k-r}\\ &=\binom dk \sum_{r=0}^d\binom{d-n}r\binom{n-d}{d-k-r}\\ &=\binom dk \binom 0{d-k}\\ &=\begin{cases}1\quad \text{if}\quad d=k \\0\quad \text{otherwise}\end{cases} \end{align}\qquad$$ as $$\binom 0{d-k}=\begin{cases}1\quad \text{for}\quad d-k=0\\ 0\quad\text{otherwise}\end{cases}$$

$\endgroup$
  • $\begingroup$ Nice solution. Nevertheless the status of $n$ should be mentioned. (+1) $\endgroup$ – Markus Scheuer Aug 3 '15 at 8:45
  • $\begingroup$ @MarkusScheuer - Thanks for the comment and upvote. Please feel free to edit the solution as suggested. $\endgroup$ – hypergeometric Aug 3 '15 at 16:11
  • $\begingroup$ How do you get $\dbinom{n-d-1+r}{r} = \dbinom{n-d-1+r}{n-d-1}$ ? The symmetry of binomial coefficients holds when the "numerator" is nonnegative, but is $n-d-1+r$ necessarily nonnegative here? $\endgroup$ – darij grinberg Aug 4 '15 at 22:00

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.