Let $x\geq 66$ be an integer and consider set $S = \{1,2,3,4....,x\}$

(1) $k$ is an integer with $66\leq k\leq x$. How many $66$-element subsets of $S$ are there whose largest element is equal to $k$?

(2) Use the answer in first part to prove -

$$\sum {k-1\choose 65}={x\choose 66}$$

I think the answer of part 1 is $k$ chooses $66$ because that way $k$ will be in all subsets. Since $k \leq 66$, $k$ will be the largest in each subset. Is there anything wrong with my logic? For part 2, I'm not sure how to go about proving that equation. Can anyone guide me to the right direction? Thanks.

  • $\begingroup$ Please check if my edit has changed your question. I'm not exactly sure about part 2. $\endgroup$
    – BlackAdder
    Jan 29, 2014 at 7:20
  • $\begingroup$ Yes, that's my question. Thank you! $\endgroup$
    – user124659
    Jan 29, 2014 at 8:11

1 Answer 1


Your answer to Part 1 is incorrect. Here's a hint.

To be concrete, let's take the example of $k = 100$.

If you want to choose a subset with $66$ elements whose largest element is $100$, what are you allowed to choose freely?

  • $\begingroup$ I'm allowed to choose 65 and the last position would be for k. $\endgroup$
    – user124659
    Jan 29, 2014 at 7:48
  • $\begingroup$ 65 elements of what set? $\endgroup$
    – user124636
    Jan 29, 2014 at 7:55
  • $\begingroup$ 65 elements that are less than k?I'm thinking about not considering k, instead just create 65-elements with those numbers less than k. $\endgroup$
    – user124659
    Jan 29, 2014 at 8:07
  • $\begingroup$ Yes. How many numbers are there less than $k$? $\endgroup$
    – user124636
    Jan 29, 2014 at 8:12
  • $\begingroup$ Ok I think I got it. It's (k-1) choose 65 because k is 100 and we don't need to consider k so that's k-1. right? $\endgroup$
    – user124659
    Jan 29, 2014 at 8:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .