Results 1 to 4 of 4

Math Help - Combinatorial proof

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    26

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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<k. 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.

    This Wikipedia page lists the following property:

    \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    Quote Originally Posted by Defunkt View Post
    Note that (according to the first post, anyway), we should be looking for a combinatorial proof, not an algebraic one.
    You are right.

    Quote Originally Posted by Defunkt View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 01:42 PM
  2. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 21st 2010, 02:47 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: August 18th 2010, 04:08 AM
  4. Another combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 5th 2010, 06:23 AM
  5. Combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 4th 2010, 08:02 PM

Search Tags


/mathhelpforum @mathhelpforum