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$
15
  • 1
    $\begingroup$ There is a $\dbinom{d}{k}$ in the sum that does not depend on $j$? $\endgroup$ Jul 31, 2015 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$ Jul 31, 2015 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$ Jul 31, 2015 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, 2015 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, 2015 at 16:14

2 Answers 2

5
+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$
1
  • $\begingroup$ @JohnWiltshire-Gordon:Thanks a lot for accepting my answer and granting the bounty. Best regards, $\endgroup$
    – epi163sqrt
    Aug 2, 2015 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$
3
  • $\begingroup$ Nice solution. Nevertheless the status of $n$ should be mentioned. (+1) $\endgroup$
    – epi163sqrt
    Aug 3, 2015 at 8:45
  • $\begingroup$ @MarkusScheuer - Thanks for the comment and upvote. Please feel free to edit the solution as suggested. $\endgroup$ Aug 3, 2015 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$ Aug 4, 2015 at 22:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .