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.
 A: 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.
A: 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.
A: To show this you can use the the binomial theorem 
which is $(x+y)^n=\sum_{k=0}^{n}\dbinom{n}{n-k}x^{n-k}y{k}$
set x=1 y=-1
and you get
$\dbinom{n}{0}-\dbinom{n}{1}+\dbinom{n}{2}.....+(-1)^{n}\dbinom{n}{0}$
$\dbinom{n}{0}+\dbinom{n}{2}=\dbinom{n}{1}+\dbinom{n}{3}$
thus in a set the number of subsets which are even equal odd subset. 
