Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Please help!

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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
4  
@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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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