Interpretation of a combinatorial identity involving iterated binomial coefficients

I am trying to find an combinatorial interpretation for the following combinatorial identity involving iterated binomial coefficients, which appeared in the November 1980 edition of The American Math Monthly:

$\dbinom{\binom{n}{b}}{2}=\displaystyle\sum_{j=1}^b\dbinom{\binom{b}{j}+e_j}{2}\binom{n+b-j}{2b},$

where $e_j=\frac{1+(-1)^{j+1}}{2}$, that is, $e_j=1$ if $j$ is odd, and $0$ otherwise.

Essentially, the left hand side of the identity can be interpreted as the number of ways to choose 2 $b$-element subsets of $\{1,2,\cdots,n\}$. What I am interested in is the derivation of the right hand side of the identity; I have read the proof in The American Math Monthly, and the author mentioned that the expression $\binom{n+b-j}{2b}$ refers to the selection of $2b$ objects from the original set $\{1,2,\cdots,n\}$, augmented by the adjunction of $b-j$ "jokers", where $0\leq j\leq b-1$, to allow for the fact that the intersection of two distinct $b$-element subsets of $\{1,2,\cdots,n\}$ can have a minimum and a maximum cardinality of $0$ and $b-1$ respectively.

What I am struggling to understand here is the expression $\dbinom{\binom{b}{j}+e_j}{2}$; how does one interpret this expression? Alternatively, is there any other way for which one can prove the identity? Personally, I have proven via a combination of combinatorial and algebraic methods that the identity does hold for small values of $b$, but the expression is not that tractable for large values of $b$.

Solution 1:

Suppose we seek to evaluate (the term for $j=0$ is zero) $$\frac{1}{2} \sum_{j=0}^b \left({b\choose j} + e_j\right) \left({b\choose j} + e_j-1\right) {n+b-j\choose 2b}.$$

This sum has four components, call them $A,B,C$ and $D.$

We have $$A = \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j}^2 {n+b-2j\choose 2b},$$ and $$B = - \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j} {n+b-2j\choose 2b},$$ and $$C = \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j+1}^2 {n+b-2j-1\choose 2b},$$ and finally $$D = \frac{1}{2} \sum_{j=0}^{b/2} {b\choose 2j+1} {n+b-2j-1\choose 2b}.$$

Starting with $A$ we put (we will use this substitution several times with different values of $b$ and $j$)

$${b\choose 2j} = \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z^{2j+1}} \; dz$$

to get for the sum $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \sum_{j=0}^{b/2} {b\choose 2j} {n+b-2j\choose 2b} \frac{1}{z^{2j}} \; dz.$$

For the inner sum we get $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n+b}}{w^{2b+1}} \sum_{j=0}^{b/2} {b\choose 2j} \frac{1}{z^{2j}(1+w)^{2j}} \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n+b}}{w^{2b+1}} \left(\left(1+\frac{1}{z(1+w)}\right)^b + \left(1-\frac{1}{z(1+w)}\right)^b\right) \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1} z^b} \left(\left(z+zw+1\right)^b + \left(z+zw-1\right)^b\right) \; dw .$$

This lets us evaluate $B$ which has $z=1$ to obtain $$-\frac{1}{4} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \left(\left(w+2\right)^b + \left(w\right)^b\right) \; dw.$$

We get for $C$ the integral $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \sum_{j=0}^{b/2} {b\choose 2j+1} {n+b-2j-1\choose 2b} \frac{1}{z^{2j+1}} \; dz.$$

The inner sum here evaluates to $$\frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1} z^b} \left(\left(z+zw+1\right)^b - \left(z+zw-1\right)^b\right) \; dw .$$

This lets us evaluate $D$ which has $z=1$ to obtain $$+\frac{1}{4} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \left(\left(w+2\right)^b - \left(w\right)^b\right) \; dw.$$

It follows that $B+D$ is $$-\frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} w^b\; dw = -\frac{1}{2} {n\choose b}.$$

On the other hand $A+C$ is $$\frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1} z^b} \left(z+zw+1\right)^b \; dw \; dz \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \left(\frac{1+z}{z}+w\right)^b \; dw \; dz.$$

This is $$\frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \frac{(1+z)^b}{z} \sum_{q=0}^b {b\choose q} \left(\frac{1+z}{z}\right)^q w^{b-q} \; dz \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\gamma} \sum_{q=0}^b {b\choose q} \frac{(1+z)^{b+q}}{z^{q+1}} w^{b-q} \; dz \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \sum_{q=0}^b {b\choose q} {b+q\choose q} w^{b-q} \; dw \\ = \frac{1}{2} \frac{1}{2\pi i} \int_{|w|=\epsilon} \sum_{q=0}^b {b\choose q} {b+q\choose q} \frac{(1+w)^{n}}{w^{b+q+1}} \; dw.$$

This finally yields $$\frac{1}{2} \sum_{q=0}^b {b\choose q} {b+q\choose q} {n\choose b+q} = \frac{1}{2} \sum_{q=0}^b {b\choose q} \frac{n!}{b!q!(n-b-q)!} \\ = \frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} \frac{(n-b)!}{q!(n-b-q)!} = \frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} {n-b\choose q} \\ = \frac{1}{2} {n\choose b} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-b}}{v} \sum_{q=0}^b {b\choose q} \frac{1}{v^q} \; dv \\ = \frac{1}{2} {n\choose b} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-b}}{v} \left(1+\frac{1}{v}\right)^b \; dv \\ = \frac{1}{2} {n\choose b} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n}}{v^{b+1}} \; dv = \frac{1}{2} {n\choose b}^2.$$

The conclusion is that $$A+B+C+D = \frac{1}{2} {n\choose b}^2 - \frac{1}{2} {n\choose b} = \frac{1}{2} {n\choose b} \left({n\choose b}-1\right),$$

which was to be shown.

Another instance of the Egorychev method is at this MSE link.

Addendum Tue Apr 14 21:38:00 CEST 2015. As per the comments we can evaluate $B+D$ as follows. $$B+D = -\frac{1}{2} \sum_{j=0}^b {b\choose j} (-1)^j {n+b-j\choose 2b}.$$

Using the standard integral substitution from above this yields $$-\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n+b}}{v^{2b+1}} \sum_{j=0}^b {b\choose j} (-1)^j \frac{1}{(1+v)^j}\; dv \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n+b}}{v^{2b+1}} \left(1-\frac{1}{1+v}\right)^b \; dv \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n+b}}{v^{2b+1}} \left(\frac{v}{1+v}\right)^b \; dv \\ = -\frac{1}{2} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n}}{v^{b+1}} \; dv = -\frac{1}{2}{n\choose b}.$$

Solution 2:

Here is an answer using formal power series that is somewhat simpler than the first one. We start as before:

$$\frac{1}{2} \sum_{j=0}^b \left({b\choose j} + e_j\right) \left({b\choose j} + e_j-1\right) {n+b-j\choose 2b}$$

where we have $e_j = [[j\;\text{is odd}]].$

Expanding we get three pieces, the first is

$$A = \frac{1}{2} \sum_{j=0}^b {b\choose j}^2 {n+b-j\choose 2b},$$

the second is

$$B = \frac{1}{2} \sum_{j=0}^b {b\choose j} (2e_j-1) {n+b-j\choose 2b} = \frac{1}{2} \sum_{j=0}^b {b\choose j} (-1)^{j+1} {n+b-j\choose 2b} $$

and the third

$$C = \sum_{j=0}^b e_j (e_j-1) {n+b-j\choose 2b} =0,$$

which leaves $A$ and $B.$ Starting with $A$ we observe that we must have $n\ge b$ or else the third binomial coefficient vanishes for all $j$ in the range, making for a zero contribution. We find

$$\frac{1}{2} \sum_{j=0}^b {b\choose j} [z^{b-j}] (1+z)^b [w^{n-b-j}] (1+w)^{n+b-j} \\ = \frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n+b} \sum_{j=0}^b {b\choose j} z^j w^j (1+w)^{-j} \\ = \frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n+b} \left(1+\frac{wz}{1+w}\right)^b \\ = \frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n} (1+w+wz)^b.$$

Recalling that $n\ge b$ this becomes

$$\frac{1}{2} [z^b] (1+z)^b [w^{n-b}] (1+w)^{n} \sum_{q=0}^b {b\choose q} w^q (1+z)^q \\ = \frac{1}{2} [z^b] (1+z)^b \sum_{q=0}^b {b\choose q} {n\choose n-b-q} (1+z)^q \\ = \frac{1}{2} \sum_{q=0}^b {b\choose q} {n\choose n-b-q} {b+q\choose b}.$$

Factoring the two binomials on the right we get

$$\frac{n!}{(n-b-q)! \times b! \times q!} = {n\choose b} {n-b\choose q}.$$

We continue with

$$\frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} {n-b\choose q} = \frac{1}{2} {n\choose b} \sum_{q=0}^b {b\choose q} [z^{n-b-q}] (1+z)^{n-b} \\ = \frac{1}{2} {n\choose b} [z^{n-b}] (1+z)^{n-b} \sum_{q=0}^b {b\choose q} z^q = \frac{1}{2} {n\choose b} [z^{n-b}] (1+z)^{n-b} (1+z)^b \\ = \frac{1}{2} {n\choose b}^2.$$

The piece labeled $B$ is next. We get

$$\frac{1}{2} \sum_{j=0}^b {b\choose j} (-1)^{j+1} [w^{n-b-j}] (1+w)^{n+b-j} \\ = - \frac{1}{2} [w^{n-b}] (1+w)^{n+b} \sum_{j=0}^b {b\choose j} (-1)^{j} w^j (1+w)^{-j} \\ = - \frac{1}{2} [w^{n-b}] (1+w)^{n+b} \left(1-\frac{w}{1+w}\right)^b \\ = - \frac{1}{2} [w^{n-b}] (1+w)^{n} = - \frac{1}{2} {n\choose b}.$$

We have shown that

$$A+B = \frac{1}{2} {n\choose b}^2 - \frac{1}{2} {n\choose b} = \frac{1}{2} {n\choose b} \left({n\choose b} - 1\right)$$

as claimed.

Remark. The piece $B$ was also evaluated in the first answer.