# Give a combinatorial proof

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.

-

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.

-
Is it necessary to prefix hints with HINT? I like this answer but I always think the practice of shouting HINT before you give one is a bit strange. – Ben Millwood Feb 25 '13 at 11:42
@Ben: I prefer to give an explicit signal that I am not providing a complete answer. This is partly for the benefit of the querent, and partly because on a few occasions when I’ve inadvertently failed to do so, someone (other than the querent) has complained that I didn’t answer the question. – Brian M. Scott Feb 25 '13 at 11:45
Well, fair enough. I guess I just haven't been bitten by not signposting my hints yet. – Ben Millwood Feb 25 '13 at 16:13

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.

-

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.

-