Combinatorial interpretation of identity: $\sum\limits_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2$

Solution 1:

The first identity is the particular case (for $a=b$ and $x=n$) of the identity $$ \sum_{i=0}^b \dbinom{a}{i} \dbinom{b}{i} \dbinom{x+i}{a+b} = \dbinom{x}{a} \dbinom{x}{b} , $$ which has appeared in math.stackexchange question #280481. For combinatorial proofs, see

• George E. Andrews, Identities in combinatorics, I: on sorting two ordered sets, Discrete Mathematics, Volume 11, Issue 2, 1975, Pages 97--106.

• George E. Andrews, David M. Bressoud, Identities in combinatorics III: Further aspects of ordered set sorting, Discrete Mathematics, Volume 49, Issue 3, May 1984, Pages 223--236.

I also give an algebraic proof in Proposition 3.39 (f) of my Notes on the combinatorial fundamentals of algebra (search for "assortment of other identities" if the numbering has changed, or else look at the archived version of 10 January 2019).

The second identity is the particular case (for $d=2b$) of the following identity: $$ \sum_{j=0}^b \left(-1\right)^j \dbinom{b}{j} \dbinom{n+j}{d} = \left(-1\right)^b \dbinom{n}{d-b} , $$ where $d$ and $b$ are two nonnegative integers and $n$ is an arbitrary (e.g., rational) number. This can be easily proven by induction over $b$. Alternatively, one can WLOG assume that $n \in \left\{d, d+1, d+2, \ldots\right\}$, and then apply some symmetry and upper negation to reduce it to the Vandermonde convolution. For yet another proof, try using finite differences (the necessary ideas are in Marc van Leeuwen's answer https://math.stackexchange.com/a/381939/ ). This does not give a combinatorial proof, but it makes me suspect that it is well-known, and hopefully someone has collected combinatorial proofs of such identities.

Solution 2:

By way of enrichment permit me to present an algebraic proof.

Suppose we seek to verify that $$\sum_{j=0}^b {b\choose j}^2 {n+j\choose 2b} = {n\choose b}^2.$$ where $0\le b\le n.$

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

and $${n+j\choose 2b} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{2b+1}} (1+w)^{n+j} \; dw.$$

This yields for the sum $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{1-z} \sum_{j=0}^b {b\choose j} (1+w)^j \frac{z^j}{(1-z)^j} \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{1-z} \left(1+\frac{(1+w)z}{1-z}\right)^b \; dz \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+w)^{n}}{w^{2b+1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} \frac{1}{(1-z)^{b+1}} (1+wz)^b \; dz \; dw.$$

The inner residue is $$\sum_{q=0}^b {b\choose q} w^q {b-q+b\choose b}.$$ Substitute this into the outer integral to get $$\sum_{q=0}^b {b\choose q} {2b-q\choose b} {n\choose 2b-q}.$$

Observe that $${2b-q\choose b}{n\choose 2b-q} = \frac{(2b-q)!}{b! (b-q)!}\frac{n!}{(2b-q)! (n-2b+q)!} \\ = \frac{(n-b)!}{b! (b-q)!}\frac{n!}{(n-b)! (n-2b+q)!} = {n\choose b} {n-b\choose b-q}.$$

This yields for the sum $${n\choose b} \sum_{q=0}^b {b\choose q} {n-b\choose b-q}.$$

which evaluates to $${n\choose b}^2$$ by inspection.

It can also be done with the integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b-q+1}} (1+z)^{n-b} \; dz$$

which yields $${n\choose b} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} (1+z)^{n-b} \sum_{q=0}^b {b\choose q} z^q \; dz \\ = {n\choose b} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{b+1}} (1+z)^{n} \; dz = {n\choose b}^2.$$

Solution 3:

Combinatorial proof of the second identity

Let $B$ be a $b$-element set and let $N$ be an $n$-element set disjoint to $B$.

The sum $\sum_j\binom b{b-j}\binom{n+j}{2b}$ counts the number of pairs of sets $T\subset B$, $X\subset N\cup B$ s.t. $|X|=2b$ and $X\cap T=\varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $T\subset B$ and then $2b$-element set $X\subset N\cup(B\setminus T)$.) And LHS counts such pairs with signs $(-1)^{|B \setminus T|}$.

Now there is a sign-reversing involution: find the smallest element of $B\setminus X$ and then add it to $T$ if it's not already in $T$, otherwise remove it from $T$. So in LHS everything with non-empty $B\setminus X$ cancels out; and there are exactly $\binom nb$ variants with $X\supset B$ and they are counted with sign $(-1)^b$.

(And the RHS is, in fact, $(-1)^b\binom nb$.)