1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @GrigoryM If you are working on this one I will not attempt it. $\endgroup$ – Marko Riedel 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$ – Greg Martin Jan 9 '15 at 23:18
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Marko Riedel 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
1
$\begingroup$

We will see that there are two cases, one when $r\gt q$ and a second case when $r\le q.$

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

There are two components here, the first of which is $$2^q\sum_{k=0}^{\lfloor r/2\rfloor} {r\choose 2k} {k\choose q} (-1)^{2k}.$$

Introduce the integral representation $${k\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^k}{z^{q+1}} \; dz$$ which gives for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{2^q}{z^{q+1}} \sum_{k=0}^{\lfloor r/2\rfloor} {r\choose 2k} (1+z)^k\; dz$$ which is $$\frac{2^{q-1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \left((1+\sqrt{1+z})^r+(1-\sqrt{1+z})^r\right) \; dz.$$

Now put $1+z = w^2$ so that $dz = 2w\; dw$ to get $$\frac{2^{q-1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w^2-1)^{q+1}} \left((1+w)^r+(1-w)^r\right) \; 2w\;dw.$$ This is $$\frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w^2-1)^{q+1}} \left((1+w)^r+(1-w)^r\right) \; ((w+1)-1)\;dw.$$ or $$\frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^q (w-1)^{q+1}} \left((1+w)^r+(1-w)^r\right) \; dw \\ - \frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^{q+1} (w-1)^{q+1}} \left((1+w)^r+(1-w)^r\right) \; dw.$$

We will now continue assuming that $r> q$ when this simplifies to $$\frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^{q-r} (w-1)^{q+1}}\; dw \\ - \frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^{q+1-r} (w-1)^{q+1}} \; dw.$$ This becomes $$\frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{(2+w-1)^{r-q}}{ (w-1)^{q+1}}\; dw \\- \frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{(2+w-1)^{r-q-1} }{(w-1)^{q+1}} \; dw \\ = \frac{2^r}{2\pi i} \int_{|w-1|=\epsilon} \frac{(1+(w-1)/2)^{r-q}}{ (w-1)^{q+1}}\; dw \\- \frac{2^{r-1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{(1+(w-1)/2)^{r-q-1} }{(w-1)^{q+1}} \; dw \\ = 2^{r-q} {r-q\choose q} - 2^{r-1-q} {r-q-1\choose q}.$$

Now return to the second part of the sum which is $$2^q\sum_{k=0}^{\lceil r/2\rceil-1} {r\choose 2k+1} {k+1/2\choose q} (-1)^{2k+1}.$$

Introduce the integral representation $${k+1/2\choose q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{k+1/2}}{z^{q+1}} \; dz = \frac{1}{2\pi i} \int_{|z|=\epsilon} \sqrt{1+z} \frac{(1+z)^k}{z^{q+1}} \; dz$$ which gives for the sum $$-\frac{2^q}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \sum_{k=0}^{\lceil r/2\rceil-1} {r\choose 2k+1} (1+z)^k \sqrt{1+z}\; dz$$ which is $$-\frac{2^{q-1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+1}} \left((1+\sqrt{1+z})^r-(1-\sqrt{1+z})^r\right) \; dz.$$ Using the same substitution as before we get $$-\frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^q (w-1)^{q+1}} \left((1+w)^r-(1-w)^r\right) \; dw \\ + \frac{2^q}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^{q+1} (w-1)^{q+1}} \left((1+w)^r-(1-w)^r\right) \; dw.$$

When $r>q$ the terms in $(1-w)^r$ do not contribute and we get the same value as for the first component. Because of the minus sign on the second component the two components cancel and the target sum evaluates to zero.

We now treat the case when $r\le q.$ Adding the two integrals for the two components we get $$\frac{2^{q+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^q (w-1)^{q+1}} (1-w)^r \; dw \\ - \frac{2^{q+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^{q+1} (w-1)^{q+1}} (1-w)^r \; dw.$$

This is $$\frac{(-1)^r 2^{q+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^q (w-1)^{q+1}} (w-1)^r \; dw \\ - \frac{(-1)^r 2^{q+1}}{2\pi i} \int_{|w-1|=\epsilon} \frac{1}{(w+1)^{q+1} (w-1)^{q+1}} (w-1)^r \; dw \\ = \frac{(-1)^r 2^{q+1}}{2\pi i \times 2^q} \int_{|w-1|=\epsilon} \frac{1}{(1+(w-1)/2)^q (w-1)^{q-r+1}} \; dw \\ - \frac{(-1)^r 2^{q+1}}{2\pi i \times 2^{q+1}} \int_{|w-1|=\epsilon} \frac{1}{(1+(w-1)/2)^{q+1} (w-1)^{q-r+1}} \; dw = (-1)^r \left({q-r+q-1\choose q-1} (-1)^{q-r}\frac{1}{2^{q-1-r}} - {q-r+q\choose q} (-1)^{q-r}\frac{1}{2^{q-r}} \right) \\ = \frac{(-1)^q}{2^{q-r}} \left(2{2q-r-1\choose q-1} - {2q-r\choose q}\right) \\ = \frac{(-1)^q}{2^{q-r}} {2q-r\choose q} \left(2\frac{q}{2q-r} - 1\right) \\ = \frac{(-1)^q}{2^{q-r}} {2q-r\choose q} \left(\frac{2q-(2q-r)}{2q-r}\right) \\ = \frac{(-1)^q}{2^{q-r}} \frac{r}{2q-r} {2q-r\choose q}.$$

$\endgroup$
  • $\begingroup$ Thank you for the answer, it seems to require quite a lot of work. I should clearly study the integral representations more. $\endgroup$ – 655321 Jan 10 '15 at 2:26
1
$\begingroup$

As per the comment by @GrigoryM to be wary of long proofs I am presenting a radical simplification of my first post, which in retrospect looks to be poor quality work. In particular the split into even and odd sum indices is completely unnecessary.

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|=\epsilon} \frac{(1+z)^{k/2}}{z^{q+1}} \; dz$$

which gives for the sum

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \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|=\epsilon} \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 $$\frac{1}{2\pi i} \int_{|w-1|=\epsilon} \frac{2^q}{(w^2-1)^{q+1}} (1-w)^r \; 2w \; dw \\ = \frac{(-1)^r}{2\pi i} \int_{|w-1|=\epsilon} \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|=\epsilon} \frac{2^{q+1}}{(w+1)^{q}(w-1)^{q+1-r}} \; dw \\- \frac{(-1)^r}{2\pi i} \int_{|w-1|=\epsilon} \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|=\epsilon} \frac{2^{q+1}}{(2+w-1)^{q}(w-1)^{q+1-r}} \; dw \\- \frac{(-1)^r}{2\pi i} \int_{|w-1|=\epsilon} \frac{2^{q+1}}{(2+w-1)^{q+1}(w-1)^{q+1-r}} \; dw \\ = \frac{(-1)^r}{2\pi i} \int_{|w-1|=\epsilon} \frac{2}{(1+(w-1)/2)^{q}(w-1)^{q+1-r}} \; dw \\- \frac{(-1)^r}{2\pi i} \int_{|w-1|=\epsilon} \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 as before 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.$

$\endgroup$

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.