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.
  • $\begingroup$ I like it! Thanks! $\endgroup$ – 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}.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.