There are a lot of combinatorial sums that one can prove with a combinatorial interpretation like double counting. For example
\begin{align*}
\begin{array}{c}
\displaystyle{\sum_{k = 0}^n \binom{n}{k} = 2^n}\\
\text{The number of the subsets of $\{1, \ldots, n\}$}
\end{array}\\
\ \\
\hline
\end{align*}
\begin{align*}
\begin{array}{c}
\displaystyle{\sum_{j = 0}^k \binom{m}{j}\binom{n}{k – j} = \binom{m + n}{k}}\\
\text{Choose $k$ balls from a bag that includes $m$ red balls and $n$ blue balls}
\end{array}\\
\ \\
\hline
\end{align*}
\begin{align*}
\begin{array}{c}
\displaystyle{\sum_{k = 0}^n k\binom{n}{k}^2} = n\binom{2n-1}{n-1}\\
\text{Create a group of $n$ students with a boy as the leader from $n$ girls and $n$ boys}
\end{array}\\
\ \\
\hline
\end{align*}
\begin{align*}
\begin{array}{c}
\displaystyle{\sum_\limits{k = 1}^n \frac{1}{2k – 1}\binom{2k}{k}\binom{2n – 2k}{n – k} = \binom{2n}{n}}\\
\text{The number of permutations of $n$ digits $0$ and $n$ digits $1$}
\end{array}\\
\ \\
\hline
\end{align*}
And similar ones. But when there's a coefficient $(-1)^k$ or $(-1)^{n – k}$ in the sum, the problem is more complicated and there aren't many ideas for giving a solution. For examples
\begin{align*}
&\text{(A)} && \sum_{k = 0}^n (-1)^{n-k}\binom{2n}{k}^2 = \binom{2n}{n}\\
&\text{(B)} && \sum_{k = 0}^n (-1)^{n – k}\binom{n}{k}\binom{mk}{n} = m^n\\
&\text{(C)} && \sum_{k = 0}^{\lfloor n/2 \rfloor} (-1)^k \binom{n – k}{k}2^{n – 2k} = n + 1
\end{align*}
My Question
Do you know any combinatorial interpretation for sums like $\text{(A), (B), or (C)}$? I know that for simpler identities like $\sum_{k = 0}^n (-1)^k\binom{n}{k} = 0$, by considering odd and even subsets we can prove the identity, but I couldn't apply the same idea to more complicated identities. Also, I think that the Inclusion-Exclusion Principle that has an alternating sum in its formula could be used here, but how?
Any idea and combinatorial approach for the general situation or especially, for $\text{(A), (B), or (C)}$ will appreciate. Note that I don't want to use other methods like generating functions, WZ pairs, or binomial expansion. Thanks.
Best Answer
Using a sign-reversing involution is a common way to give a combinatorial proof of equations involving a summation with alternating sign. A
I can do no better than to quote this answer directly: https://math.stackexchange.com/a/3401952/499816
C
For this, we can also use a sign-reversing involution. Consider counting the number of ways to tile a $1\times n$ rectangle with $1\times 1$ squares, where each square can be either white or black, and with $1\times 2$ dominos, where the dominos only come in one color. If you use $k$ dominos, then there will be $n-2k$ squares, so $n-k$ tiles total. There are $\binom{n-k}k$ ways to choose the locations of the dominos, and then $2^{n-2k}$ ways to choose the colors of the squares. The parity of a tiling is determined by the parity of the number of dominos.
The sign-reversing involution is to find the first instance of either a domino, or a white square immediately followed by a black square. If the first is a domino, then you replace that domino with a white square followed by a black square, and if it is a white square followed by a black square, you replace those two squares with a domino. The only tilings are not canceled out are the ones without dominos, and without any white squares immediately followed by black squares. There are $n+1$ such exceptional tilings, namely the tilings which are $j$ black squares followed by $n-j$ white squares, for each $j\in \{0,1,\dots,n\}$.
B
For this, we use an inclusion-exclusion argument. Both sides answer the following question.
The easy answer is $m^n$; each column gets exactly one shaded square, and there are $m$ squares in each of the $n$ columns.
To explain the alternating sum, let $U$ be the set of ways to shade in $n$ squares of the grid, without the column restriction, so $|U|=\binom{mn}{n}$. For each $i\in \{1,\dots,n\}$, let $S_i$ be the set of colorings in $U$ where the $i^{th}$ column is unshaded. We are trying to count $|S_1^c\cap S_2^c\cap \dots \cap S_n^c|$. Using the principle of inclusion-exclusion, the answer is $$ \sum_{k=0}^n(-1)^k\binom{n}{k}|S_1\cap \dots \cap S_k|, $$ provided that when $k=0$, you interpret the empty intersection as $|U|$. It should be clear that $|S_1\cap \dots \cap S_k|=\binom{m(n-k)}n$, since the $n$ shaded squares can be freely chosen from the remaining $n-k$ columns. Plugging that in above and reversing the order of summation leads to desired summation, completing the proof.