# 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. Jan 9 '15 at 22:38
• @Marko tomorrow (or later) — maybe; if you have time now — please just go ahead Jan 9 '15 at 22:40
• @GrigoryM you are right, question corrected Jan 9 '15 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) Jan 9 '15 at 22:41
• Mathematica might know the "WZ-method". You could learn about that or - probably more accessible - generating functions. Jan 9 '15 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.

• (+1). Thanks for alerting me politely to the perils of long proofs. I have posted another version of your above remarks which is a significant improvement over my first attempt. Jan 11 '15 at 23:01
• 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). Jan 15 '15 at 2:53
• @655321 I'm afraid I don't know a good reference... Jan 15 '15 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 Jan 15 '15 at 19:24

Suppose we seek to evaluate $$2^q\sum_{k=0}^r {r\choose k} {k/2\choose q} (-1)^k.$$

Introduce the integral representation $${k/2\choose q} = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{(1+z)^{k/2}}{z^{q+1}} \; dz$$

which gives for the sum (the branch cut from the square root for $$k$$ odd is $$(-\infty, -1]$$ and we have analyticity in a neighborhood of the origin)

$$\frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{2^q}{z^{q+1}} \sum_{k=0}^r {r\choose k} (-1)^k (1+z)^{k/2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\varepsilon} \frac{2^q}{z^{q+1}} (1-\sqrt{1+z})^r \; dz.$$

Now put $$1+z=w^2$$ so that $$dz = 2w \; dw$$ to get (with $$w = \sqrt{1+z} = 1 + 1/2 z \pm \cdots$$ the image of $$|z|=\varepsilon$$ makes one turn)

$$\frac{1}{2\pi i} \int_{|w-1|=\gamma} \frac{2^q}{(w^2-1)^{q+1}} (1-w)^r \; 2w \; dw \\ = \frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{2^{q+1} (w+1-1)}{(w+1)^{q+1}(w-1)^{q+1-r}} \; dw \\ = \frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{2^{q+1}}{(w+1)^{q}(w-1)^{q+1-r}} \; dw \\- \frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{2^{q+1}}{(w+1)^{q+1}(w-1)^{q+1-r}} \; dw.$$

We need some more algebra here, getting $$\frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{2^{q+1}}{(2+w-1)^{q}(w-1)^{q+1-r}} \; dw \\- \frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{2^{q+1}}{(2+w-1)^{q+1}(w-1)^{q+1-r}} \; dw \\ = \frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{2}{(1+(w-1)/2)^{q}(w-1)^{q+1-r}} \; dw \\- \frac{(-1)^r}{2\pi i} \int_{|w-1|=\gamma} \frac{1}{(1+(w-1)/2)^{q+1}(w-1)^{q+1-r}} \; dw.$$

These last two can be evaluated by inspection to give $$(-1)^r \left(2\times \frac{(-1)^{q-r}}{2^{q-r}}{q-r+q-1\choose q-1} -\frac{(-1)^{q-r}}{2^{q-r}}{q-r+q\choose q} \right) \\ = 2^{r-q} \times (-1)^q \left(2\times {2q-r-1\choose q-1} - {2q-r\choose q}\right).$$

This simplifies to $$\frac{(-1)^q}{2^{q-r}} \frac{r}{2q-r} {2q-r\choose q}.$$

Note once more that this only holds when $$r\le q.$$ (When $$r\gt q$$ the pole at $$w=1$$ from the integral in $$w$$ vanishes and we get zero.) Concerning the integrals, the image of $$|z|=\varepsilon$$ is contained in an annulus defined by two circles centered at one of radius $$1-\sqrt{1-\varepsilon}$$ and $$\sqrt{1+\varepsilon}-1 \lt \varepsilon.$$ This ensures that the pole at $$w=-1$$ is definitely not inside the contour. We may shrink the image to a circle $$|w-1|=\gamma$$ where $$\gamma = \varepsilon/2.$$

• I asked a similar or almost the same question at math.stackexchange.com/questions/4235171/…. It is also worth reading my question and its answers, because seemingly there is more extensive answers there. Sep 6 at 14:44