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!

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