Prove that the sum of an alternating combinatorial sequence is equal to zero. The sum of the binomial coefficients of $(x+y)^n$ can be expressed as follows:
$$\sum_{k=0}^n\binom{n}{k}=2^n$$
This can be shown to be the case using a double counting proof of all the ways of choosing subsets of a set of $n$ distinct elements. The alternating version of this sum can be shown to be equal to zero:
$$\sum_{k=0}^n(-1)^k\binom{n}{k}=0$$
There are many proofs of this statement that I am aware of. A more general version of the first sum can be expressed as follows:
$$\sum_{k=q}^n\binom{n}{k}\binom{k}{q}=2^{n-q}\binom{n}{q}$$
where $n>q$. The proof of this equality also involves a double counting proof of all the ways of choosing subsets of size at least $q$ out of a set of $n$ distinct elements and then selecting $q$ elements in each one of those subsets. Notice that if $q=0$ then this sum reduces to the original sum. Now what I want to prove is that the alternating version of this sum is also equal to zero, namely:
$$\sum_{k=q}^n(-1)^k\binom{n}{k}\binom{k}{q}=0$$
I have tried to get this sum to "telescope" to zero or to somehow express it in terms of the original alternating series, all to no avail. Any help in proving the identity above would be greatly appreciated.
 A: The first alternating sum is the special case $x=-1$ of the general identity
$$
\sum_{k=0}^n x^k\binom{n}{k}=(1+x)^n
$$
(as long as we assume $n>0$).
Similarly, the second alternating sum is the special case $x=-1$ of the general identity
$$
\sum_{k=q}^n x^k\binom{n}{k}\binom{k}{q} = \binom nq x^q(1+x)^{n-q}
$$
(as long as we assume $n>q$).
A: Consider the sum
$$\sum_{k=q}^n x^k\binom{n}{k}\binom{k}{q}$$
We can use the factorial definition of binomial coefficients to get the following identity
$$\binom{n}{k}\binom{k}{q}$$
$$\frac{n!k!}{k!q!(n-k)!(k-q)!}$$
$$\frac{n!}{q!(n-k)!(k-q)!}$$
$$\frac{n!}{q!(n-k)!(k-q)!}\cdot\frac{(n-q)!}{(n-q)!}$$
$$\binom{n}{q}\binom{n-q}{k-q}$$
So our sum simplifies to
$$\binom{n}{q}\sum_{k=q}^nx^k\binom{n-q}{k-q}$$
We can shift the indices to get
$$\binom{n}{q}\sum_{k=0}^{n-q}x^{k+q}\binom{n-q}{k}$$
$$\binom{n}{q}x^q\sum_{k=0}^{n-q} x^k\binom{n-q}{k}$$
Clearly the remaining summation is $(1+x)^{n-q}$ by binomial theorem, so the expression is equivalent to
$$\boxed{\binom{n}{q}x^q(1+x)^{n-q}}$$
We can plug in $x=-1$ to prove the desired identity.
A: Say a team consists of total $k$ players where $q$ of them are in the starting lineup. You can pick the members first and then select some of them to be in the starting lineup or you can select the starting lineup first and then pick some members to complete the team. Therefore the following is true:
$$
\binom{n}{k}\cdot\binom{k}{q}=\binom{n}{q}\cdot\binom{n-q}{k-q}
$$
Substitute this into the expression of interest then we get familiar identity:
$$
\begin{align}
\sum_{k=q}^{n}{\left(-1\right)^{k}\binom{n}{k}\cdot\binom{k}{q}}&=\left(-1\right)^{q}\binom{n}{q}\sum_{k-q=0}^{n-q}{\left(-1\right)^{k-q}\binom{n-q}{k-q}}\\
\\
&= \left(-1\right)^{q}\binom{n}{q}\cdot 0\\
\\
&=0
\end{align}
$$
