1
$\begingroup$

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.

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

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?

$\endgroup$
6
  • $\begingroup$ I'm allowed to choose 65 and the last position would be for k. $\endgroup$
    – user124659
    Jan 29 '14 at 7:48
  • $\begingroup$ 65 elements of what set? $\endgroup$
    – user124636
    Jan 29 '14 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 '14 at 8:07
  • $\begingroup$ Yes. How many numbers are there less than $k$? $\endgroup$
    – user124636
    Jan 29 '14 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 '14 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.