# Proving binomial summation identity using generating functions

An exercise for class requires me to prove the following identity using generating functions: $$\sum_{k=0}^{m/2} (-1)^k {n \choose k} {n+m-2k-1 \choose n-1} = {n \choose m}$$ for all $m \leq n$ and $m$ is even. I've tried a bunch of things but can't wrap my head around this one.

I assume one would start with $${\sum_{k=0}^{n} {n \choose m}} x^m = (1+x)^n = \frac{(1-x^2)^n}{(1-x)^n}$$ and then interpreting the expression on the right as the product of generating functions to somehow arrive at $$\sum_{m=0}^{n} \left( \sum_{k=0}^{m/2} (-1)^k {n \choose k} {n+m-2k-1 \choose n-1} \right) x^m$$ but now idea how to actually do it.

Some help would be greatly appreciated! :-)

• What class is this? – marty cohen Oct 15 '15 at 21:16
• It's Undergraduate Discrete Mathematics – Philipp Arndt Oct 19 '15 at 4:44

Suppose we seek to evaluate

$$\sum_{k=0}^{\lfloor m/2\rfloor} (-1)^k {n\choose k} {n+m-2k-1\choose n-1}$$

where $n\ge m.$

Re-write this as $$\sum_{k=0}^{\lfloor m/2\rfloor} (-1)^k {n\choose k} {n+m-2k-1\choose m-2k}.$$

Now introduce $${n+m-2k-1\choose m-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-2k+1}} (1+z)^{n+m-2k-1} \; dz.$$

Observe that this is zero when $2k\gt m$ so we may extend the range of $k$ to infinity.

We thus get for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{n+m-1} \sum_{k\ge 0} {n\choose k} (-1)^k \frac{z^{2k}}{(1+z)^{2k}}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{n+m-1} \left(1-\frac{z^2}{(1+z)^2}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1+z)^{n-m+1}} \left(1+2z\right)^n \; dz.$$

Extracting the residue we get $$\sum_{q=0}^m {n\choose q} 2^q {m-q+n-m\choose m-q} (-1)^{m-q} \\ = \sum_{q=0}^m {n\choose q} 2^q {n-q\choose m-q} (-1)^{m-q}.$$

To conclude introduce the integral $${n-q\choose m-q} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-q+1}} (1+z)^{n-q} \; dz.$$

Observe that this is zero when $q\gt m$ so we may extend the range of $q$ to infinity to get

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{n} \sum_{q\ge 0} {n\choose q} 2^q (-1)^{m-q} \frac{z^q}{(1+z)^q} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(-1)^m}{z^{m+1}} (1+z)^{n} \left(1-2\frac{z}{1+z}\right)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(-1)^m}{z^{m+1}} \left(1-z\right)^n \; dz = (-1)^m {n\choose m} (-1)^m = {n\choose m}.$$

Alternative solution.

Introduce $${n+m-2k-1\choose n-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m-2k+1}} \frac{1}{(1-z)^n} \; dz.$$

This is again zero when $2k\gt m.$ We get for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1-z)^n} \sum_{k\ge 0} {n\choose k} (-1)^k z^{2k}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} \frac{1}{(1-z)^n} (1-z^2)^n \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^n \; dz \\ = {n\choose m}.$$

This is probably what the problem had in mind.