Finite summation with binomial coefficients, $\sum (-1)^k\binom{r}{k} \binom{k/2}{q}$ 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.
 A: 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.
A: 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

*

*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.

*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.

