Help with binomial identity

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.

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

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)