Problem 6. Prove the following identity involving combinations: For any n 2 1, t
ID: 3069867 • Letter: P
Question
Problem 6. Prove the following identity involving combinations: For any n 2 1, the following is true: Tn Hint: While there are several possible ways to establish this identity (including algebraic manipulation and induction), consider the following simpler approach based on counting. Try to come up with a combinatorial interpretation of either side of the equation and show that these are the same. In this case, suppose we have a set S-11,2,...,n), what does the right hand side of (1) mean with respect to this set? And, now what is a possible interpretation of the left hand side that matches this?Explanation / Answer
Let us suppose we have a set S = {1,2,....,n}. Now we count the number of ways of selecting numbers from set S, such that we can select any number of numbers from the set, even 0. Hence selecting no number at all, is also a way.
Now we interpret the left hand side of the given expression:
(nC0) : selecting 0 numbers from the set S
(nC1) : selecting 1 number from the set S
.....
(nCn) : selecting n numbers from the set S.
LHS gives every possible way of selecting numbers from the set S.
Now let's interpret the right hand side of the expression.
While selecting the numbers from the set S = {1,2,...k,......,n}. We look at each number one at a time, say 'k'. We have two choices: either to select it or leave it, i.e 2 ways. Just like that, we have 2 ways for every n numbers.
So total number of ways of selecting numbers from the set S = 2 x 2 x 2 x 2...( n times) = 2n.
Since both RHS and LHS gives the same interpretation of seecting any number of numbers from the set S, we deduce that LHS = RHS