Results 1 to 2 of 2

Math Help - A binomial identity

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    48
    Awards
    1

    A binomial identity

    I'm trying to give a combinatorial proof of the following identity:

    \sum_{k=0}^{n} 2^k \binom{n}{k} \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}=\binom{2n+1}{n}


    ***

    On the right side, \binom{2n+1}{n} is the number of n-element subsets of a (2n+1)-element set, or the number of ways we can select n different balls from a box containing (2n+1) balls...

    The left side doesn't seem so straightforward. Let's say we have an n-element set, and we wish to find the number of ways we can form a k-element subset, where k=0,1,...n, and the number of ways we can pick a subset of that newly-formed k-element set.
    As a k-element set has 2^k subsets, we can do this procedure in 2^k \cdot \binom{n}{k} ways, for some k.
    But the next factor, \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor} is totally baffling. I'm not even sure that the above interpretation is correct. And the next problem would be to show that the whole left side of the problem, in fact, equals \binom{2n+1}{n}.

    Many thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Let S be a set with 2n+1 elements. Partition S into n pairs of elements, with one single element left over. We want to choose a set of n elements from S. From each pair of elements we can select 0, 1 or 2 elements. Also, we can either select or not select the single element.

    Start by selecting k pairs to choose one element from. There are \textstyle2^k\binom nk ways of doing this ( \textstyle\binom nk ways of choosing which pairs, and 2 ways of choosing which element in each pair). To bring the total number of selected elements up to n, we then need to select both elements from exactly half of the remaining n-k pairs, if n-k is even. If n-k is odd then we have to select both elements from \lfloor \tfrac{n-k}{2} \rfloor of them, together with the single element of S. In either case, there are \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor} ways of doing this.

    That shows that \sum_{k=0}^{n} 2^k \binom{n}{k} \binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}=\binom{2n+1}{n}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] An identity of equivalent products related to the binomial theorem
    Posted in the Differential Geometry Forum
    Replies: 8
    Last Post: September 20th 2010, 12:53 AM
  2. Proving a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 16th 2009, 04:56 PM
  3. Binomial coefficiens: an identity
    Posted in the Math Challenge Problems Forum
    Replies: 2
    Last Post: April 13th 2009, 06:04 PM
  4. Combinatorial proof of a binomial identity
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 12th 2008, 03:42 PM
  5. Identity using binomial theorem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 2nd 2008, 10:41 AM

Search Tags


/mathhelpforum @mathhelpforum