# Math Help - Combinatorial proof

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 $\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 $k$-object subsets from $n$ elements. I.e., when we are taking about combinations $n\choose k$, usually $n\ge k$; ${n\choose k}=0$ when $n. When we are talking about combinations with repetitions $\left(\!\!{n\choose k}\!\!\right)$, which is the number of ways to put $k$ objects into $n$ bins, $k$ may be greater than $n$.

$\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 $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.