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).