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

Currently, I am trying to prove the following two identities, which arose as a result of my other question in the Math StackExchange recently:

$$$$\sum_{j=0}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2$$$$

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

In particular, the first identity appeared as a remark in Volume 4 of Henry Gould's Combinatorial Identities.

Out of curiosity, I am wondering if there is a combinatorial proof for any of these two identities?

EDIT: I have managed to prove the second identity, by considering the coefficient of $$x^{n-b}$$ in the expansion of $$(1+x)^{-(b+1)}=(1+x)^b(1+x)^{-(2b+1)}$$.

EDIT 2: I have also managed to find a proof for the first identity by using the Vandermonde identity. I would still be interested however, in a proof of the second identity using a more combinatorial approach.

• I'm not sure if this is going anywhere at all, but in the first identity, the RHS is the number of ways to pick two subsets of $\{ 1,2, \ldots , n \}$ with $b$ elements. I was trying to come up with a bijection to get to the LHS; my intuition is that maybe the $j$ on the LHS represents the number of elements that the two sets have in common, but I wasn't able to get anywhere with that. – Marcus M Apr 15 '15 at 2:48

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

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.

• (+1). The references and observations are a good improvement of the page. – Marko Riedel Sep 28 '15 at 1:44

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

### 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$$.)

• I guess this argument also applies to the generalization $\sum\limits_{j=0}^b \left(-1\right)^j \dbinom{b}{j} \dbinom{n+j}{d} = \left(-1\right)^b \dbinom{n}{d-b}$ ? – darij grinberg Sep 28 '15 at 1:48
• (Re: generalization) indeed – Grigory M Oct 1 '15 at 14:14