# Sum of product of binomial coefficients

I would like to compute the following sum: $$\sum_{k=0, \, k =odd}^{\min\{2n, m\}} {2n \choose 2n-k}{2m-2n \choose m-k}$$ So far I can prove that $$\sum_{k=0, \, k =odd}^m {2n \choose 2n-k}{2m-2n \choose m-k}=\frac 12 {2m \choose m}+(-1)^{m+1}2^{2m-1}{n-\frac 12 \choose m}.$$ which can be proven by splitting sum as $$\sum_{k=0, \, k =odd}^m {2n \choose 2n-k}{2m-2n \choose m-k}= \frac 12 \sum_{k=0}^m {2n \choose 2n-k}{2m-2n \choose m-k}-\frac 12 \sum_{k=0, }^m (-1)^k{2n \choose 2n-k}{2m-2n \choose m-k}$$ and computing first sum using Chu-Vandermond identity and second -- using notion of coefficient-extractor.

I am not sure on how to proceed when the upper bound of summation is $$\min\{2n,m\}$$.

• It does not matter whether the upper bound is $2n$ or $m$ or $\min\left\{2n,m\right\}$. The only addends that are covered by one but not the other are $0$. (Here I'm assuming that $n$ and $m$ are nonnegative integers.) – darij grinberg Oct 15 '20 at 18:02
• After the split, you should not have $k$ odd as restrictions because $\sum_k a_{2k+1} = \sum_k (1-(-1)^k) a_k/2$. – RobPratt Oct 15 '20 at 18:07
• @darijgrinberg What you say is OK for $m\geqslant n$, but I believe the case $m<n$ is also relevant, no? – მამუკა ჯიბლაძე Oct 15 '20 at 18:40
• @მამუკაჯიბლაძე The first binomial coefficient in the product is $0$ if $k > 2n$, while the second is $0$ if $k > m$. Thus, the product is $0$ in either casse. – darij grinberg Oct 15 '20 at 18:53
• @darijgrinberg When $m<n$ then, denoting $2(n-m)=d$, I believe the second one is $\binom{-d}{m-k}=(-1)^{m-k}\binom{m-k+d-1}{d-1}$, no? This might well be nonzero for $k>m$. – მამუკა ჯიბლაძე Oct 15 '20 at 19:07

Mathematica tells me that

$$\sum_{k=0, \, k =\text{odd}}^{2n} {2n \choose 2n-k}{2m-2n \choose m-k}=2 n \binom{2 m-2 n}{m-1}+\binom{2 m-2 n}{m}$$ $$\qquad+ \, _4F_3\left(\frac{1}{2}-\frac{m}{2},1-\frac{m}{2},\frac{1}{2}-n,1-n;\frac{3}{2},\frac{m}{2}-n+1,\frac{m}{2}-n+\frac{3}{2};1\right).\qquad(1)$$

Moreover, $$\sum_{k=0, \, k =\text{odd}}^{m} {2n \choose 2n-k}{2m-2n \choose m-k}=\binom{2 m-2 n}{m}$$ $$\qquad+\frac{2^{2 m-1}}{m!} \left(\frac{\Gamma \left(m+\frac{1}{2}\right)}{\sqrt{\pi }}-\frac{\Gamma \left(m-n+\frac{1}{2}\right)}{\Gamma \left(\frac{1}{2}-n\right)}\right), \qquad(2)$$ which differs from the answer $$\frac 12 {2m \choose m}+(-1)^{m+1}2^{2m-1}{n-\frac 12 \choose m}$$ given in the OP.
For example, for $$n=1,m=2$$, both left-hand-side and right-hand-side of equation (2) evaluate to 5, while the answer in the OP evaluates to 4.