Register to reply 
Combinatorial Proofs of a binomial identity 
Share this thread: 
#1
Mar110, 07:43 PM

PF Gold
P: 117

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^(nm) 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
Mar210, 02:02 AM

P: 111

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
[tex] \sum_{k = m}^n \binom{n}{k} \binom{k}{m} [/tex] 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 [tex] 2^{n  m} \binom{n}{m} [/tex] such ordered pairs. Thus, since both methods count the same thing, you have [tex] \sum_{k = m}^n \binom{n}{k} \binom{k}{m} = 2^{n  m} \binom{n}{m} \textrm{.} [/tex] 


Register to reply 
Related Discussions  
Combinatorial Proofs of Binomial Identities  Calculus & Beyond Homework  9  
Plz help with this combinatorial identity  Precalculus Mathematics Homework  2  
A combinatorial identity  General Math  0  
Proving Combinatorial identity  Introductory Physics Homework  2  
Combinatorial Identity  Introductory Physics Homework  1 