Alternative Proof of Vandermode Convolution

Question

I'm working through the book Discrete Calculus: Methods for Counting by Carlo Mariconda and Alberto Tonolo, and I had a question about one of the problems in the book.

The problem is 8.3 and says: Use generating formal series to give an alternative proof of the formula (2.57.a): $\sum_{l\in\mathbb{Z}} {r\choose m+l}{s\choose n+l} = {r+s\choose r-m+n}, \forall m,n,r,s\in\mathbb{N}$

Formula 2.57.a is Vandermone's Convolution, given as $\sum_{j=0}^k {m\choose j}{n\choose k-j} = {m+n\choose k}$.

I've convinced myself these two are equal but setting $j=r-(m+l)$ and then $k=r-m+n$ via substitution.

What I can't figure out, however, is the proof. I've looked at the solutions offered by Mariconda and Tonolo (which I am grateful for), which I've attached here.

Solution

I'm confused about two points with this solution. First, I don't see how it's equivalent to finding the $(m+n)$th coefficient of the convolution product. For instance, if I take r=s=m=n=1, and do the sum of above, I get 2, not 1 which is the $X^2$ coefficient of the given convolution product.

Secondly, I'm confused about the last step at the end. How do they go from ${r+s\choose m+n}$ to ${r+s\choose r-m+n}$?

I feel there's several steps missing and I can't figure it out and it's really causing me to go crazy. Are there perhaps typos? There's an errata page on their website for the book (https://discretecalculus.wordpress.com/), but there's no file there with errata. Or am I just missing something?

I'd appreciate any help, thanks!

Answer 1

It seems the authors don't claim that $[X^{n+m}](1+X)^{r+s}$ is the solution of the formula (2.57a) but they rather want us to recall the Vandermonde identity and that the formula (2.57a) follows as a certain variation of it.

On the one hand, we can show formula (2.57a) is a variation of Vandermonde's identity. Since formula (2.57a) is symmetric in $m$ and $n$ we assume in the following wlog $0\leq m\leq n$. We obtain \begin{align*} \color{blue}{\sum_{l\in\mathbb{Z}}\binom{r}{m+l}\binom{s}{n+l}} &=\sum_{l=-m}^{r-m}\binom{r}{m+l}\binom{s}{n+l}\tag{1.1}\\ &=\sum_{l=0}^r\binom{r}{l}\binom{s}{n+l-m}\tag{1.2}\\ &=\sum_{l=0}^{r+n-m}\binom{r}{l}\binom{s}{r+n-m-l}\tag{1.3}\\ &\,\,\color{blue}{=\binom{r+s}{r+n-m}}\tag{1.4} \end{align*} where the last step follows thanks to Vandermonde's identity.

Comment:

• In (1.1) we set lower and upper limit of the sum by recalling the binomial coefficient $\binom{p}{q}$ is zero if the lower index $q<0$ and also if $q>p$.

• In (1.2) we shift the index to start with $l=0$.

• In (1.3) we change the order of summation $l\to r-l$ and set the upper limit of the sum according to the binomial coefficient with upper index $s$.

Generating functions:

Starting with (1.2) we derive formula (2.57a) using generating functions. We use the coefficient of operator $[X^n]$ to denote the coefficient of a series $A(X)$. We obtain \begin{align*} \color{blue}{\sum_{l=0}^r}&\color{blue}{\binom{r}{l}\binom{s}{l+n-m}}\\ &=\sum_{l=0}^r\binom{r}{l}[X^{l+n-m}](1+X)^s\tag{2.1}\\ &=[X^{n-m}](1+X)^s\sum_{l=0}^r\binom{r}{l}X^{-l}\tag{2.2}\\ &=[X^{n-m}](1+X)^s\left(1+X^{-1}\right)^r\tag{2.3}\\ &=[X^{r-m+n}](1+X)^{r+s}\tag{2.4}\\ &\,\,\color{blue}{=\binom{r+s}{r-m+n}}\tag{2.5} \end{align*} and the claim follows.

Comment:

• In (2.1) we use the coefficient of operator as in $\binom{p}{q}=[X^q](1+X)^p$.

• In (2.2) we use $[X^{p-q}]A(X)=[X^p]X^qA(X)$.

• In (2.3) we use the binomial theorem.

• In (2.4) we apply the rule as in (2.2) and do some simplifications.

• In (2.5) we select the coefficient of $X^{r-m+n}$.