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.

  • 1
    $\begingroup$ @GrigoryM If you are working on this one I will not attempt it. $\endgroup$ Jan 9 '15 at 22:38
  • $\begingroup$ @Marko tomorrow (or later) — maybe; if you have time now — please just go ahead $\endgroup$
    – Grigory M
    Jan 9 '15 at 22:40
  • $\begingroup$ @GrigoryM you are right, question corrected $\endgroup$
    – 655321
    Jan 9 '15 at 22:41
  • $\begingroup$ 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) $\endgroup$
    – Grigory M
    Jan 9 '15 at 22:41
  • $\begingroup$ Mathematica might know the "WZ-method". You could learn about that or - probably more accessible - generating functions. $\endgroup$ 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.

  • $\begingroup$ (+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. $\endgroup$ Jan 11 '15 at 23:01
  • $\begingroup$ 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). $\endgroup$
    – 655321
    Jan 15 '15 at 2:53
  • $\begingroup$ @655321 I'm afraid I don't know a good reference... $\endgroup$
    – Grigory M
    Jan 15 '15 at 19:22
  • $\begingroup$ @655321 though there is one example that is explained in detail in many books (e.g. in Enumerative Combinatorics): Lagrange inversion formula $\endgroup$
    – Grigory M
    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.$


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.