Finite summation with binomial coefficients, $\sum (-1)^k\binom{r}{k} \binom{k/2}{q}$

Question

I came across the following finite sum involving (generalized) binomial coefficients:

$$ 2^q \sum_{k=0}^r \binom{r}{k} \binom{k/2}{q} (-1)^k .$$

Putting this into Mathematica gives me:

$$ (-1)^q 2^{r-q} \left( \binom{2q-r-1}{q-1} - \binom{2q-r-1}{q} \right) $$

and I'm interested in how could this solution be derived. There seems to be some binomial coefficient magic going on which I don't understand.

So far I have made very little progress, I noticed that the $2^q \binom{k/2}{q} = \frac{1}{q!} \prod_{i=0}^{q-1} (k-2i)$ -term looks a bit like a double factorial but this didn't get me very far. There also seems to be a lot of identities for sums involving $ \binom{r}{k} (-1)^k $ but I haven't found anything useful for this case.

Answer 1

Since I am a Bear of Very Little Brain, and long proofs Bother me, let me post slightly shorter version of essentially the same proof.

$2^q\sum_{k=0}^r(-1)^k\binom rk\binom{k/2}q$ is the coefficient of $z^q$ in the expansion of $(1-\sqrt{1+2z})^r=\left(\frac{-2z}{1+\sqrt{1+2z}}\right)^r$.

Now we want to substitue $\sqrt{1+2z}$ by $1+w$. There is a purely algebraic lemma for this, but one way to establish it is to write this coefficient as a (complex) integral and apply the change of variables formula for integrals: \begin{multline} \DeclareMathOperator{\res}{res} %\res\,(1-\sqrt{1+2z})^r\frac{dz}{z^{q+1}}= \res\left(\frac{-2z}{1+\sqrt{1+2z}}\right)^r\frac{dz}{z^{q+1}}= (-2)^r\res\frac1{(1+\sqrt{1+2z})^r}\frac{dz}{z^{q-r+1}}=\\ (-2)^r\res\frac1{2+w}\frac{dw+w\,dw}{(w+w^2/2)^{q-r+1}}= (-1)^r2^{2r-q-1} \res\frac1{(2+w)^{q-r+1}}\frac{dw+w\,dw}{w^{q-r+1}}. \end{multline} (here $\res_z=\frac1{2\pi i}\oint_{|z|=\epsilon}$, if you will; since $z=w+w^2/2$, $dz=dw+w\,dw$).

So we get a sum of two binomial coefficients (each multiplied by $(-1)^\cdots2^\cdots$) — that's the answer Mathematica gave you.

Answer 2

Let $\mathbb{N}_0=\{0,1,2,\dotsc\}$.

• For $m,n\in\mathbb{N}_0$, we have \begin{equation}\label{Wilf-Lemma2.2}\tag{1} \sum_{k=0}^{n}(-1)^{k} \binom{n}{k}\binom{k/2}{m} = \begin{cases} 0, & n>m\in\mathbb{N}_0;\\ \displaystyle (-1)^{m}n!\frac{[2(m-n)-1]!!}{(2m)!!}\binom{2m-n-1}{2(m-n)}, & m\ge n\in\mathbb{N}_0. \end{cases} \end{equation}
• For $m,n\in\mathbb{N}_0$, we have \begin{equation}\tag{2} \sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\binom{2k}{m} = \begin{cases} 0, & n>m\in\mathbb{N}_0;\\\displaystyle (-1)^n\binom{n}{m-n}2^{2n-m}, & m\ge n\in\mathbb{N}_0. \end{cases} \end{equation}
• For $m\ge n\in\mathbb{N}_0$, we have \begin{equation}\tag{3} \sum_{n=0}^m\sum_{k=0}^{n}(-1)^{k} \binom{n}{k}\binom{k/2}{m} =(-1)^m\frac{(2m-1)!!}{(2m)!!}. \end{equation}

(A1) The proof of the identity \eqref{Wilf-Lemma2.2} can be found in Lemma 2.2 and its proof in the paper [1] below.

References

1. Feng Qi and Mark Daniel Ward, Closed-form formulas and properties of coefficients in Maclaurin's series expansion of Wilf's function, arXiv (2021), available online at https://arxiv.org/abs/2110.08576v1.
2. Siqintuya Jin, Bai-Ni Guo, and Feng Qi, Partial Bell polynomials, falling and rising factorials, Stirling numbers, and combinatorial identities, Computer Modeling in Engineering & Sciences (2022), in press; accepted on 24 January 2022; available online at https://dx.doi.org/10.32604/cmes.2022.019941 or https://www.researchgate.net/publication/358050501.