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?

  • 1
    $\begingroup$ similar: math.stackexchange.com/questions/94514/… $\endgroup$ – ulead86 Dec 17 '12 at 12:23
  • $\begingroup$ @ulead86: How is that related? $\endgroup$ – joriki Dec 17 '12 at 12:24
  • $\begingroup$ I tried reading that - didn't seem like the same question in first look. $\endgroup$ – Mark Dec 17 '12 at 12:24
  • $\begingroup$ sorry, changed the link (wrong copy+paste) $\endgroup$ – ulead86 Dec 17 '12 at 12:25
  • 1
    $\begingroup$ @ulead86: Unfortunately the new link seems just as unrelated as the other one. $\endgroup$ – 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?


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

  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Dec 17 '12 at 15:59
  • $\begingroup$ @Marc: Sorry for being overly brief; I thought this would work as a hint, but apparently it didn't; I've spelled it out. $\endgroup$ – 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.$$

  • $\begingroup$ I'm not sure I agree with "very straightforwardly", but +1 for a nice proof :-) $\endgroup$ – joriki Jul 20 '15 at 6:50
  • $\begingroup$ Thanks. This is the so-called Egorychev method although some of it is probably folklore, Observe the mechanics at this MSE link. $\endgroup$ – Marko Riedel Jul 20 '15 at 16:42
  • $\begingroup$ Pretty amazing! I wonder why I'd never come across this method before. $\endgroup$ – joriki Jul 20 '15 at 20:44
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel Jul 20 '15 at 21:21
  • $\begingroup$ 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 :-) $\endgroup$ – joriki Jul 20 '15 at 21:33

Another way to do this is to use snake oil. Use $m$ as a new free variable (for $n - 1$), notice that outside the given range the first binomial coefficient is zero, and write the generating function for the sum we want:

$\begin{align} \sum_{m \ge 0} z^m \sum_k (-1)^k \binom{n}{k} \binom{2 n - 2 k}{m} &= \sum_k (-1)^k \binom{n}{k} \sum_{m \ge 0} \binom{2 n - 2 k}{m} z^m \\ &= \sum_k (-1)^k \binom{n}{k} (1 + z)^{2 n - 2 k} \\ &= (1 + z)^{2 n} \sum_k (-1)^k \binom{n}{k} (1 + z)^{- 2 k} \\ &= (1 + z)^{2 n} \left(1 - (1 + z)^{-2}\right)^n \\ &= \left((1 + z)^2 - 1\right)^n \\ &= z^n (2 + z)^n \end{align}$

Now we want the coefficient of $z^m$ of this:

$\begin{align} [z^m] z^n (2 + z)^n &= [z^{m - n}] (2 + z)^n \\ &= \binom{n}{m - n} 2^{n - (m - n)} \\ &= \binom{n}{m - n} 2^{2 n - m} \end{align}$

The original problem asks for $m = n - 1$, sure enough, $\binom{n}{-1} = 0$.

Note: The $[z^n]$ notation is described by Knuth as a simpler way to handle Egorychev's "method of coefficients", which I believe is what Marko Riedel is doing.


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.