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\}$.

  • $\begingroup$ 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.) $\endgroup$ Oct 15, 2020 at 18:02
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Oct 15, 2020 at 18:07
  • $\begingroup$ @darijgrinberg What you say is OK for $m\geqslant n$, but I believe the case $m<n$ is also relevant, no? $\endgroup$ Oct 15, 2020 at 18:40
  • $\begingroup$ @მამუკაჯიბლაძე 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. $\endgroup$ Oct 15, 2020 at 18:53
  • 1
    $\begingroup$ @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$. $\endgroup$ Oct 15, 2020 at 19:07

1 Answer 1


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.


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.