Register to reply

Combinatorial Proofs of a binomial identity

by silvermane
Tags: combinatorics, identities, proof
Share this thread:
Mar1-10, 07:43 PM
PF Gold
silvermane's Avatar
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^(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 :)
Phys.Org News Partner Science news on
Mysterious source of ozone-depleting chemical baffles NASA
Water leads to chemical that gunks up biofuels production
How lizards regenerate their tails: Researchers discover genetic 'recipe'
Mar2-10, 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
\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{.}

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