Originally Posted by
uberbandgeek6 I'm really confused about the last question in this problem:
Let S = {1, 2, . . . , n}.
a) Suppose that k and i are integers such that 1 <= k <= i <= n. How many subsets of S of size k have i as their largest element?
b) How many total subsets of S are of size k?
c) Combining your answers to (a) and (b), explain how this proves the following formula for any positive integers k <= n (there are some binomial coefficients that I will right as "(x)C(y)" here, as well as a sigma-notation series):
n
Sigma ( (i-1)C(k-1) ) = (n)C(k)
i=k
For (a), I am limited to i elements, and must choose k of them, so the answer would be (i)C(k), or so I think.
For (b), there are n total elements, and I must choose k of them, so the answer would be (n)C(k).
I'm really not sure where to even begin with (c).