Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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{.}
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook