A combinatorial proof that the alternating sum of binomial coefficients is zero

I came across the following problem in a book:

Give a combinatorial proof of $$ {n \choose 0} + {n \choose 2} + {n \choose 4} + \, \, ... \, = {n \choose 1} + {n \choose 3} + {n \choose 5} + \, \, ...$$ using the "weirdo" method (i.e., where one of the elements is chosen as special and included-excluded -- I'm sure you get the idea).

After days of repeated effort, the proof has failed to strike me. Because every time one of the elements is excluded, the term would be ${n-1 \choose k}$ and not $ {n \choose k}$, which is not the case in either of the sides of the equation.

Solution 1:

HINT: Let $A$ be a set of $n$ marbles. Paint one of the marbles red; call the red marble $m$. If $S$ is a subset of $A$ that does not contain $m$, let $S'=S\cup\{m\}$, and if $m\in S\subseteq A$, let $S'=S\setminus\{m\}$. Show that the map $S\mapsto S'$ yields a bijection between the subsets of $A$ with even cardinality and those with odd cardinality.

Solution 2:

This is not a direct combinatorial proof but one can make the argument combinatorial. There is an easy combinatorial proof of the following: $${n\choose {k}}={{n-1}\choose {k}}+{{n-1}\choose {k-1}}$$ Now take $k=2r$ and $k=2r+1$ and sum over all integers $r$. In the first case you will have the expression in the LHS and for the second you will get an expression for RHS and both are equal by the above identity.