Htykuut

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

begin{equation}
sum_{j=0}^bbinom{b}{j}^2binom{n+j}{2b}=binom{n}{b}^2
end{equation}

begin{equation}
sum_{j=0}^b(-1)^jbinom{b}{j}binom{n+j}{2b} = left(-1right)^b binom{n}{b}
end{equation}

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.

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 7 November 2018).

The second identity is the particular case (for $d=2b$) of the following identity:
$$
sum_{j=0}^b left(-1right)^j dbinom{b}{j} dbinom{n+j}{d} = left(-1right)^b dbinom{n}{d-b} ,
$$
where $n$ and $b$ are two nonnegative integers and $d$ is an integer.
This is some applications of symmetry and upper negation away from the Vandermonde convolution (and can also be easily proven by induction over $b$). 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.

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

Suppose we seek to verify that
$$sum_{j=0}^b {bchoose j}^2
{n+jchoose 2b} = {nchoose b}^2.$$
where $0le ble n.$

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

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

This yields for the sum
$$frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}}
frac{1}{1-z}
sum_{j=0}^b {bchoose j} (1+w)^j frac{z^j}{(1-z)^j}
; dz ; dw
\ = frac{1}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi 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}{2pi i}
int_{|w|=epsilon} frac{(1+w)^{n}}{w^{2b+1}}
frac{1}{2pi 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 {bchoose q} w^q {b-q+bchoose b}.$$
Substitute this into the outer integral to get
$$sum_{q=0}^b {bchoose q} {2b-qchoose b}
{nchoose 2b-q}.$$

Observe that
$${2b-qchoose b}{nchoose 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)!}
= {nchoose b} {n-bchoose b-q}.$$

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

which evaluates to
$${nchoose b}^2$$
by inspection.

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

which yields
$${nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n-b}
sum_{q=0}^b {bchoose q} z^q ; dz
\ = {nchoose b} frac{1}{2pi i}
int_{|z|=epsilon} frac{1}{z^{b+1}} (1+z)^{n} ; dz
= {nchoose 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_jbinom b{b-j}binom{n+j}{2b}$ counts the number of pairs of sets $Tsubset B$, $Xsubset Ncup B$ s.t. $|X|=2b$ and $Xcap T=varnothing$. (Indeed, one summand corresponds to choosing first $(b-j)$-element set $Tsubset B$ and then $2b$-element set $Xsubset Ncup(Bsetminus T)$.) And LHS counts such pairs with signs $(-1)^{|B setminus T|}$.

Now there is a sign-reversing involution: find the smallest element of $Bsetminus 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 $Bsetminus X$ cancels out; and there are exactly $binom nb$ variants with $Xsupset B$ and they are counted with sign $(-1)^b$.

(And the RHS is, in fact, $(-1)^bbinom nb$.)