# Cousin of the Vandermonde binomial identity

The Vandermonde binomial identity can be expressed as \begin{align*} \sum_{i+j=r} \binom{m}{i} \binom{n}{j} = \binom{m+n}{r} && r \leq m +n. \end{align*} While working on an algebra problem, I stumbled on a formally similar, but distinct identity: \begin{align*} \sum_{i+j=r} \binom{i}{m}\binom{j}{n} = \binom{r+1}{m+n+1} && m+n \leq r. \end{align*} This isn't hard to prove or anything. The left-hand side enumerates the subsets $S \subseteq \{1,2,\ldots,r+1\}$ with $|S| = m+n+1$ according to the position of the $(m+1)$st largest element of $S$. But, I found the similarity striking enough to ask the following

Question: Are the parallels between these two formulas just a coincidence? Or, is there something else going on here?

This is not a complete explanation but this observation might be helpful:

Consider the sum $$S(s,r)= \sum_{m+n=s}\sum_{i+j=r} \binom{m}{i} \binom{n}{j},$$ with $r\leq s$.

Using the first formula, it becomes $$S(s,r) = \sum_{m+n=s} \binom{s}{r} = (s+1) \binom{s}{r} = \frac{(s+1)!}{r!(s-r)!}.$$ On the other hand, changing the order of summation and using the second fromula, it becomes $$S(s,r) = \sum_{i+j=r} \binom{s+1}{r+1} = (r+1) \binom{s+1}{r+1} = \frac{(s+1)!}{r!(s-r)!}.$$

This suggests that there might be a nice way of calculating $S(s,r)$ (or perhaps a combinatorial interpretation of $S(s,r)$) that shows an intuitive relationship between the formulas you gave.

There is indeed a combinatorial interpretation:

Consider a set of $s+1$ people. $$\{1,2,\ldots,s+1\}$$ We want to count the number of ways to select one chairperson and $r$ committee members from this set.

• Directly, there are $(s+1) \cdot \binom{s}{r}$ ways to do this.
• Indirectly, if $x$ is the chairperson, then there are $m$ people to the left of $x$ and $n$ people to the right of $x$ where $m+n=s$, the remaining people who could be on the committee. We now tally up the possible committees conditional on there being $i$ people selected from the left-hand group and $j=r-i$ selected from the right-hand group.
• I like it! Thanks! – Mike F Mar 13 '14 at 5:03

It can be adjusted to be a convolution by shifting the upper and lower indices and then there must be a formal power series $f(x)$ for which the second identity

equates the $x^t$ terms in $f(x)^p f(x)^q = f(x)^{p+q}$,

just as the first identity compares the $x^r$ coefficients of $(1+x)^m (1+x)^n = (1+x)^{m+n}$.

Taking $(I,J,R,M,N) = (i+1, j+1, r+2, m+1, n+1)$ the formula becomes

\begin{align*} \sum_{I+J=R} \binom{I-1}{M-1}\binom{J-1}{N-1} = \binom{R-1}{M+N-1} && M+N \leq R. \end{align*}

which now has the correct form $\sum_{I+J=R} c(M,I)c(N,J) =c(M+N,R)$

for $c(p,q)={{q-1} \choose {p-1}}$.

We can read off $f(x)$ as $\sum c(1,v)x^v = 0 + x + x^2 + x^3 + \dots = \frac{x}{1-x}$ , with $(t,p,q)=(R,M,N)$ and write everything in the original variables. The identity

equates the $x^{r+2}$ coefficients of $\hskip10pt (\frac{x}{1-x})^{m+1}(\frac{x}{1-x})^{n+1} = (\frac{x}{1-x})^{m+n+2}.$

Cancelling the powers of $x$ gives a proof using the binomial theorem with negative exponents, by

equating the $x^{r-m-n}$ coefficients of $\hskip10pt (\frac{1}{1-x})^{m+1}(\frac{1}{1-x})^{n+1} = (\frac{1}{1-x})^{m+n+2}.$