Sum of binomial coefficients $\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{2n - 2k}{n - 1} = 0$ 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?
 A: 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.$$
A: 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.
A: 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$.
A: 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}.
$$
