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.

  • $\begingroup$ 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. $\endgroup$ – Ben Millwood Feb 25 '13 at 11:42
  • 6
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 25 '13 at 11:45
  • $\begingroup$ Well, fair enough. I guess I just haven't been bitten by not signposting my hints yet. $\endgroup$ – 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



thus in a set the number of subsets which are even equal odd subset.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.