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}^b\binom{b}{j}^2\binom{n+j}{2b}=\binom{n}{b}^2 \end{equation}

\begin{equation} \sum_{j=0}^b(-1)^j\binom{b}{j}\binom{n+j}{2b} = \left(-1\right)^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.

  • $\begingroup$ 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. $\endgroup$
    – Marcus M
    Apr 15, 2015 at 2:48

2 Answers 2


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.

  • $\begingroup$ (+1). The references and observations are a good improvement of the page. $\endgroup$ Sep 28, 2015 at 1:44

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

  • 1
    $\begingroup$ 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}$ ? $\endgroup$ Sep 28, 2015 at 1:48
  • $\begingroup$ (Re: generalization) indeed $\endgroup$
    – Grigory M
    Oct 1, 2015 at 14:14

You must log in to answer this question.

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