1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial Proofs of a binomial identity

  1. Mar 1, 2010 #1


    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Show that for all integers n,m where 0 ≤ m ≤ n
    The sum from k=m to n of {(nCk)*(kCm)} = (nCm)*2^(n-m)

    3. The attempt at a solution
    So for the proof, I have to use a real example, such as choosing committees, binary sequences, giving fruit to kids, etc. I have been thinking hard on it, but I don't fully understand it to do so. Any hints would be wonderful. I don't exactly want the answer, just an understanding! Thank you for your time :)
  2. jcsd
  3. Mar 2, 2010 #2
    Think about it like this: Imagine you have a big set [tex] S [/tex], with [tex] n [/tex] elements. You want to find the number of ordered pairs [tex] (A, B) [/tex], where [tex] A [/tex] and [tex] B [/tex] are subsets of [tex] S [/tex], [tex] A [/tex] has size [tex] m [/tex], and [tex] A \subseteq B [/tex]. There are two ways to count the number of such ordered pairs. You could choose the elements of [tex] B [/tex] first, by letting [tex] |B| = k [/tex] (where [tex] m \leq k \leq n [/tex]); there are then [tex] \binom{n}{k} [/tex] ways to choose [tex] B [/tex], and [tex] \binom{k}{m} [/tex] ways to pick the set [tex] A [/tex] from the elements of [tex] B [/tex]. Thus, for a given [tex] k [/tex], there are [tex] \binom{n}{k} \binom{k}{m} [/tex] ways to choose the pair [tex] (A, B) [/tex], so there are
    \sum_{k = m}^n \binom{n}{k} \binom{k}{m}
    such pairs in total.

    Alternatively, you could choose the elements of [tex] A [/tex] first. This time, there are [tex] \binom{n}{m} [/tex] ways to pick [tex] A [/tex]. Choosing [tex] B [/tex] then amounts to picking any subset [tex] C [/tex] of [tex] S \setminus A [/tex] which you then "add on" to [tex] A [/tex]: [tex] B = A \cup C [/tex]. There are [tex] 2^{|S \setminus A|} = 2^{n - m} [/tex] subsets of [tex] S \setminus A [/tex]. Thus, there are
    2^{n - m} \binom{n}{m}
    such ordered pairs. Thus, since both methods count the same thing, you have
    \sum_{k = m}^n \binom{n}{k} \binom{k}{m} = 2^{n - m} \binom{n}{m} \textrm{.}
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Combinatorial Proofs binomial Date
Please help with with this combinatorial proof! Apr 19, 2012
Combinatorial Proof Jan 17, 2012
Combinatorial Proof? May 4, 2011
Algebraic Proof of Combinatorial Identity Feb 22, 2011
Combinatorial Proofs of Binomial Identities Mar 1, 2010