Half of Vandermonde's Identity

Question

We know Vandermonde's Identity, which states

$\sum_{k=0}^{r}{m \choose k}{n \choose r-k}={m+n \choose r}$.

Does anyone know what happens if we walk bigger steps with k? Say we skip all the odd ks, is something like

$\sum_{k=0}^{r/2}{m \choose 2k}{n \choose r-2k}=\frac{1}{2} {m+n \choose r}$

or at least

$\sum_{k=0}^{r/2}{m \choose 2k}{n \choose r-2k}=\Theta \left( \frac{1}{2} {m+n \choose r}\right)$

true?

Maybe someone here has even some general insight on other step widths?

Thank you!

Answer 1

In general, having the ogf (z-Transform) $$ F(z) = \sum\limits_{0\, \le \;n} {a_{\,n} \,z^{\,n} } $$ then $$ {1 \over m}\sum\limits_{0 \le \,k\, \le \,m - 1} {\left( {z^{\,{1 \over m}} \;e^{\,i\,{{2k\pi } \over m}} } \right)^{\,j} F(z^{\,{1 \over m}} \;e^{\,i\,{{2k\pi } \over m}} )} = \sum\limits_{0\, \le \;n} {\,a_{\,m\;n - j} \,z^{\,n} } $$

But unfortunately, the truncated binomial expansion $$ \sum\limits_{0\, \le \;k} {\left( \matrix{ n \cr r - k \cr} \right)\,z^{\,k} } $$ does not have in general ($r<n$) a compact closed expression.

We can go either through the Hypergeometric version $$ \sum\limits_{\left( {0\, \le } \right)\;k\,\left( { \le \,\,r} \right)} { \binom{m}{k} \binom{n}{r-k}\,z^{\,k} } = \binom{n}{r} \;{}_2F_{\,1} \left( {\matrix{ { - m,\; - r} \cr {n - r + 1} \cr } \;\left| {\,z} \right.} \right) $$ or through the double ogf $$ \eqalign{ & G(x,y,n,m) = \sum\limits_{0\, \le \,k} {\left( {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} { \binom{m}{j}\,\binom{n}{k-j} y^{\,j} } } \right)x^{\,k} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,m} \right)} { \binom{m}{j}\left( {x\,y} \right)^{\,j} \sum\limits_{\left( {j\, \le } \right)\,k\,\left( { \le \,n} \right)\,} { \,\binom{n}{k-j}x^{\,k - j} } } = \cr & = \left( {1 + xy} \right)^{\,m} \left( {1 + x} \right)^{\,n} \cr} $$

Then for instance we have $$ \eqalign{ & \sum\limits_{0\, \le \,k} {\left( {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\left\lfloor {\min (m,k)/2} \right\rfloor } \right)\;} { \left( \matrix{ m \cr 2j \cr} \right)\,\left( \matrix{ n \cr k - 2j \cr} \right)} } \right)x^{\,k} } = \cr & = {1 \over 2}\left( {G(x,1,n,m) + G(x, - 1,n,m)} \right) = \cr & = {1 \over 2}\left( {1 + x} \right)^{\,n} \left( {\left( {1 + x} \right)^{\,m} + \left( {1 - x} \right)^{\,m} } \right) = \cr & = {1 \over 2}\left( {1 + x} \right)^{\,n + m} + {1 \over 2}\left( {1 + x} \right)^{\,n} \left( {1 - x} \right)^{\,m} = \cr & = {1 \over 2}\left( {1 + x} \right)^{\,n + m} + {1 \over 2}\left( {1 + x} \right)^{\,n - m} \left( {1 - x^{\,2} } \right)^{\,m} = \cr & = {1 \over 2}\left( {1 + x} \right)^{\,n + m} + {1 \over 2}\left( {1 - x^{\,2} } \right)^{\,{{n + m} \over 2}} \left( {{{1 + x} \over {1 - x}}} \right)^{\,{{n - m} \over 2}} \cr} $$ which clearly indicates what is the difference between $$ {1 \over 2}\binom{n+m}{r} \quad vs\quad \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\left\lfloor {\min (m,k)/2} \right\rfloor } \right)\;} { \binom{m}{2j} \, \binom{n}{r-2j} } $$

Of course the complement will be $$ \eqalign{ & \sum\limits_{0\, \le \,k} {\left( {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\left\lfloor {\min (m,k)/2} \right\rfloor } \right)\;} { \binom{m}{2j+1} \,\binom{n}{k - \left( {2j + 1} \right)}} } \right)x^{\,k} } = \cr & = {1 \over 2}\left( {G(x,1,n,m) - G(x, - 1,n,m)} \right) = \cr & = {1 \over 2}\left( {1 + x} \right)^{\,n} \left( {\left( {1 + x} \right)^{\,m} - \left( {1 - x} \right)^{\,m} } \right) \cr} $$

Answer 2

We derive a binomial identity which shows the deviation of OPs sum from $\frac{1}{2}\binom{m+n}{r}$. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. This way we can write for instance

\begin{align*} \binom{n}{k}=[z^k](1+z)^n\tag{1} \end{align*}

We assume wlog $n\geq m$ and obtain \begin{align*} \color{blue}{\sum_{k=0}^{r/2}}&\color{blue}{\binom{m}{2k}\binom{n}{r-2k}}\\ &=\sum_{k\geq 0}\binom{m}{2k}[z^{r-2k}](1+z)^n\tag{2}\\ &=[z^r](1+z)^n\sum_{k\geq 0}\binom{m}{2k}z^{2k}\tag{3}\\ &=[z^r](1+z)^n\frac{1}{2}\left((1+z)^m+(1-z)^m\right)\tag{4}\\ &=\frac{1}{2}[z^r](1+z)^{m+n}+\frac{1}{2}[z^r](1+z)^n(1-z)^m\\ &=\frac{1}{2}\binom{m+n}{r}+\frac{1}{2}[z^r](1-z^2)^m(1+z)^{n-m}\tag{5}\\ &=\frac{1}{2}\binom{m+n}{r}+\frac{1}{2}[z^r]\sum_{k=0}^{r/2}\binom{m}{k}(-1)^kz^{2k}(1+z)^{n-m}\\ &=\frac{1}{2}\binom{m+n}{r}+\frac{1}{2}\sum_{k=0}^{r/2}\binom{m}{k}(-1)^k[z^{r-2k}](1+z)^{n-m}\tag{6}\\ &\,\,\color{blue}{=\frac{1}{2}\binom{m+n}{r}+\frac{1}{2}\sum_{k=0}^{r/2}\binom{m}{k}\binom{n-m}{r-2k}(-1)^k}\tag{7} \end{align*}

Comment:

• In (2) we apply the coefficient of operator as indicated in (1) and we set the upper limit of the sum to $\infty$ without changing anything since we are adding zeros only.

• In (3) we use the linearity of the coefficient of operator.

• In (4) we write the sum as polynomial in closed form.

• In (5) we select the coefficient of $z^r$ of the left polynomial and we rewrite the other polynomial keeping in mind that $n\geq m$.

• In (6) we use the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (7) we select the coefficient of $z^{r-2k}$.