1. ## Combinatorial proof

Give a combinatorial proof of:

SUM(n choose k)= SUM(n choose k)
k odd k even

Well I know that (n choose k) represents putting k identical objects into n bins.

Perhaps I can say that k= 2r+1 for the left side and k=2r for the right side for some integer r.

Any help would be great!

2. Do you mean $\displaystyle \sum_{k\text{ is even}}{n\choose k}=\sum_{k\text{ is odd}}{n\choose k}$?

I know that (n choose k) represents putting k identical objects into n bins.
I am not sure about this. I think it is the number of ways of selecting $\displaystyle k$-object subsets from $\displaystyle n$ elements. I.e., when we are taking about combinations $\displaystyle n\choose k$, usually $\displaystyle n\ge k$; $\displaystyle {n\choose k}=0$ when $\displaystyle n<k$. When we are talking about combinations with repetitions $\displaystyle \left(\!\!{n\choose k}\!\!\right)$, which is the number of ways to put $\displaystyle k$ objects into $\displaystyle n$ bins, $\displaystyle k$ may be greater than $\displaystyle n$.

$\displaystyle \sum_{j=0}^n (-1)^j\tbinom n j = 0\qquad(12)$

which is equivalent to what you need to prove. It suggests proving it by induction on $\displaystyle n$ using the Pascal's rule.

3. Note that (according to the first post, anyway), we should be looking for a combinatorial proof, not an algebraic one.

So let's think - assume we have k identical objects and we want to put them in k out of n spots. Do you agree that choosing what spots we *will* be putting objects in is the same as choosing what spots we *won't* be putting objects in?

4. Originally Posted by Defunkt
Note that (according to the first post, anyway), we should be looking for a combinatorial proof, not an algebraic one.
You are right.

Originally Posted by Defunkt
So let's think - assume we have k identical objects and we want to put them in k out of n spots. Do you agree that choosing what spots we *will* be putting objects in is the same as choosing what spots we *won't* be putting objects in?
I see how to prove the main claim easily when n is odd, but not when n is even.