# Sum of binomial coefficients

How do I prove the following identity:

$$\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$$

I am trying to use inclusion-exclusion, and this will boil down to a sum like inclusion-exclusion, and the $\binom{2n-2k}{n-1}$ term wouldn't matter (it will be equivalent to set sizes). Is this a correct way to go?

-
–  ulead86 Dec 17 '12 at 12:23
@ulead86: How is that related? –  joriki Dec 17 '12 at 12:24
I tried reading that - didn't seem like the same question in first look. –  Mark Dec 17 '12 at 12:24
sorry, changed the link (wrong copy+paste) –  ulead86 Dec 17 '12 at 12:25
@ulead86: Unfortunately the new link seems just as unrelated as the other one. –  joriki Dec 17 '12 at 12:27

In how many ways can you select $m\lt n$ squares on a $2\times n$ board such that exactly $n$ columns contain a selected square?

[Edit:]

From the lack of upvotes and the inquiring comment of a distinguished user I conclude that I should explain this perhaps overly laconic answer.

The OP wanted to prove the result by inclusion–exclusion. The number of ways to select $m$ squares on a $2\times n$ board such that at most $j$ particular columns contain a selected square is $\binom{2j}m$. By inclusion–exclusion, if there are $a_j$ ways to do something with at most $j$ particular objects, then there are

$$\sum_{k=0}^n(-1)^k\binom nka_{n-k}$$

ways to do it with exactly $n$ objects (where the binomial coefficient counts the number of ways of selecting $n-k$ particular ones of the $n$ objects). Putting this together yields the number of ways to select $m$ squares on a $2\times n$ board such that exactly $n$ columns contain a selected square:

$$\sum_{k=0}^n(-1)^k\binom nk\binom{2n-2k}m\;.$$

Since it's impossible to have exactly $n$ columns contain a selected square if less than $n$ squares are selected, this is $0$ for $m\lt n$, and thus in particular for $m=n-1$.

-
I can answer that question easily (the answer is indeed equal to the right hand side of the equation in the original question), but I fail to see what this weird description has to do with the (more interesting) left hand side. Notably there is nothing alternating in your description. –  Marc van Leeuwen Dec 17 '12 at 15:59
@Marc: Sorry for being overly brief; I thought this would work as a hint, but apparently it didn't; I've spelled it out. –  joriki Dec 17 '12 at 16:36

The function $g:k\mapsto \binom{2n-2k}{n-1}$ is a polynomial function of degree $n-1$. The operation $f\mapsto\bigl(x\mapsto\sum_{k=0}^n(-1)^k\binom knf(x+k)\bigr)$ equals $(-1)^n\Delta^n$, where $\Delta$ is the finite difference operator $f\mapsto\bigl(x\mapsto f(x+1)-f(x)\bigr)$, which kills constant functions and lowers the degree of polynomial functions by $1$. Therefore $(-1)^n\Delta^n(g)=0$, which means that $$x\mapsto\sum_{k=0}^n(-1)^k\binom kng(x+k)$$ is the zero function. Now apply for $x=0$ to obtain $$0=\sum_{k=0}^n(-1)^k\binom kng(k) = \sum_{k=0}^n(-1)^k\binom kn\binom{2n-2k}{n-1}.$$

-

This can be done very straightforwardly and we can retain the given range of the index $k.$ Suppose we seek to evaluate $$\sum_{k=0}^n (-1)^k {n\choose k} {2n-2k\choose n-1}.$$

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

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

-
I'm not sure I agree with "very straightforwardly", but +1 for a nice proof :-) –  joriki Jul 20 at 6:50
Thanks. This is the so-called Egorychev method although some of it is probably folklore, Observe the mechanics at this MSE link. –  Marko Riedel Jul 20 at 16:42
Pretty amazing! I wonder why I'd never come across this method before. –  joriki Jul 20 at 20:44
This is basically the Cauchy Residue Theorem as used also at this MSE link. Quite possibly some consider it to be self-evident and not in need of a name or of publicity. –  Marko Riedel Jul 20 at 21:21
Well, it's one thing to know and recognize the residue theorem, quite another to come up with the idea of using it in this interesting way :-) –  joriki Jul 20 at 21:33