Cfrgtkky

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!

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)^ntag{1}
end{align*}

We assume wlog $ngeq m$ and obtain
begin{align*}
color{blue}{sum_{k=0}^{r/2}}&color{blue}{binom{m}{2k}binom{n}{r-2k}}\
&=sum_{kgeq 0}binom{m}{2k}[z^{r-2k}](1+z)^ntag{2}\
&=[z^r](1+z)^nsum_{kgeq 0}binom{m}{2k}z^{2k}tag{3}\
&=[z^r](1+z)^nfrac{1}{2}left((1+z)^m+(1-z)^mright)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 $ngeq 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}$.

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

But unfortunately, the truncated binomial expansion
$$
sumlimits_{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
$$
sumlimits_{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) = sumlimits_{0, le ,k} {left( {sumlimits_{left( {0, le } right),j,left( { le ,m} right)} {
binom{m}{j},binom{n}{k-j} y^{,j} } } right)x^{,k} } = cr
& = sumlimits_{left( {0, le } right),j,left( { le ,m} right)} {
binom{m}{j}left( {x,y} right)^{,j} sumlimits_{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{
& sumlimits_{0, le ,k} {left( {sumlimits_{left( {0, le } right),j,left( { le ,leftlfloor {min (m,k)/2} rightrfloor } 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 vsquad sumlimits_{left( {0, le } right),j,left( { le ,leftlfloor {min (m,k)/2} rightrfloor } right);} {
binom{m}{2j} , binom{n}{r-2j} }
$$

Of course the complement will be
$$
eqalign{
& sumlimits_{0, le ,k} {left( {sumlimits_{left( {0, le } right),j,left( { le ,leftlfloor {min (m,k)/2} rightrfloor } 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}
$$