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

• @GrigoryM If you are working on this one I will not attempt it. Commented Jan 9, 2015 at 22:38
• @Marko tomorrow (or later) — maybe; if you have time now — please just go ahead Commented Jan 9, 2015 at 22:40
• @GrigoryM you are right, question corrected Commented Jan 9, 2015 at 22:41
• off the top of my head, something like math.stackexchange.com/a/609202 should work (but finding a bijective proof would be, perhaps, more challenging) Commented Jan 9, 2015 at 22:41
• Mathematica might know the "WZ-method". You could learn about that or - probably more accessible - generating functions. Commented Jan 9, 2015 at 23:18

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.

• Is there like a book or an online resource that would thoroughly explain these representations of coefficients as complex integrals (residues)? I'm having bit of a hard time with those (not this one in particular, but in general). Commented Jan 15, 2015 at 2:53
• @655321 I'm afraid I don't know a good reference... Commented Jan 15, 2015 at 19:22
• @655321 though there is one example that is explained in detail in many books (e.g. in Enumerative Combinatorics): Lagrange inversion formula Commented Jan 15, 2015 at 19:24

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

• For $$m,n\in\mathbb{N}_0$$, we have $$$$\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}$$$$
• For $$m,n\in\mathbb{N}_0$$, we have $$$$\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}$$$$
• For $$m\ge n\in\mathbb{N}_0$$, we have $$$$\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)!!}.$$$$

(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.
• Could you provide a proof?
– user
Commented Oct 5, 2021 at 11:38
• @user I will provide a suitable proof, please keep patiently. Not only this answer, but also several other conclusions have been proved in a draft of a manuscript of mine. Commented Oct 6, 2021 at 13:35
• A detailed proof of this answer is the proof of Lemma 2.2 in "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 arxiv.org/abs/2110.08576v1." Commented Oct 19, 2021 at 3:23
• I would suggest you to give the reference as the part of the answer rather than a comment. It would be also useful to refer the particular page or the formula number in the manuscript.
– user
Commented Oct 19, 2021 at 13:52
• @user I will publish all proofs in officially published papers, but not here. One of reasons is that these proofs are not short and independent. Commented Oct 20, 2021 at 12:09