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$ – darij grinberg Oct 15 '20 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 '20 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 '20 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$ – darij grinberg Oct 15 '20 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 '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.


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.