2
$\begingroup$

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! :-)

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

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.

$\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.