5
$\begingroup$

today, at college, we had the following definition of $n\choose k$:

For any set $S=\{a_1,\ldots,a_n\}$ containing n elements, the number of distinct k-element subsets of it that can be formed is given by $n\choose k$.

Now I've wanted to use the definition to prove ${n-1\choose k}+{n-1\choose k-1}={n\choose k}$ for all $1\leq k and $n>1$ as an exercise. I've tried to prove by induction. So the step $n=2$ is easy. But I have difficulties with $n\rightarrow n+1$.

I've tried to split the set $S=\{a_1,\ldots,a_n,a_{n+1}\}$ into subsets:

1) containing $a_{n+1}$

2) not contaning $a_{n+1}$

The second one is easy, there are $n\choose k$ subsets. But what about the first one? And do you need anything more for the right side? I think the left side would be almost the same just n and k are different.

Thanks guys!

  • 0
    You can just write it out if you dont insist on a proof by induction.2012-10-25

4 Answers 4

2

The number of size-$k$ subsets of $\{a_1,\ldots,a_{n+1}\}$ that contain $a_{n+1}$ is the number of size-$(k-1)$ subsets of $\{a_1,\ldots,a_n\}$, thus it is $\binom{n}{k-1}$.

The number of size-$k$ subsets of $\{a_1,\ldots,a_{n+1}\}$ that do not contain $a_{n+1}$ is the number of size-$k$ subsets of $\{a_1,\ldots,a_n\}$, thus it is $\binom{n}{k}$.

Add those together to get the number of size-$k$ subsets of $\{a_1,\ldots,a_{n+1}\}$, which is $\binom{n+1}{k}$.

That's not a proof by induction though: You're not using any induction hypothesis.

  • 1
    The fact that you're insisting on induction makes me wonder whether the "definition" you're working with might be the one using factorials rather than the characterization of $\binom n k$ as the number of size-$k$ subsets of a size-$n$ set.2012-10-25
1

From a $k$-element subset of $\{1,\ldots,n+1\}$ containing $n+1$ you obtain a $(k-1)$-element subset of $\{1,\ldots,n\}$ by droping $n+1$, and vice versa by inserting $n+1$. These two maps are inverse of each other, i.e. bijections. Therefore the number of $k$-element subset of $\{1,\ldots,n+1\}$ containing $n+1$ equals the number of $(k-1)$-element subsets of $\{1,\ldots,n\}$.

1

Consider a set of $n$ blue balls and $1$ red ball. The number of ways of choosing $k$ balls from this is $\dbinom{n+1}k$. In any choice of $k$ balls, you either have the red ball (or) you do not have the red ball. Number of ways of choosing $k$ balls such that none of them is red is $\dbinom{n}k$, since all the $k$ balls have to be chosen from the $n$ blue balls. Number of ways of choosing $k$ balls such that one of them is red is $\dbinom{n}{k-1}$, since one red ball is already part of the $k$ balls and hence you need to choose $k-1$ balls from $n$ blue balls.

1

You're almost there!

For your case (1), you've already chosen 1 element for the k-element subset; how many more do you need to choose, and how large is the remaining 'pool' of elements to choose from? (Now, how many ways are there to do that?)

Finally, since your k-element subset may either (1) contain $a_{n+1}$ or (2) not contain $a_{n+1}$, the total number of ways of building it is just the sum of (1) and (2). Putting the pieces together, you're done.

This isn't induction, however: this is direct counting. For a similar problem, how many "Fat" subsets of the n-set $[n] = ${$1,2,3,...,n$} are there, where a subset $S$ is "Fat" if every element $k \in S$ is at least as big as the size of the subset, $k \geq |S|$?

  • 1
    But you do need to remind the OP that the $\binom{n-1}{n-k}$ in his formula is the same as $\binom{n-1}{k-1}$ of your proof.2012-10-25