# problem with proving a property of $n\choose k$

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<n$ 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!

-
Hint: write $\binom{n-1}{n-k}$ as $\binom{n-1}{k-1}$ and then argue that choosing a subset of size $k$ from a set of $\{a_1, \ldots, a_{n-1}\]$ of $n$ distinct objects can be done by setting $a_n$ aside and choosing $k$ objects from $\{a_1, \ldots, a_{n-1}\]$ or by choosing $k-1$ objects from the set $\{a_1, \ldots, a_{n-1}\]$ and adding in $a_n$ to make a subset of $k$ objects. – Dilip Sarwate Oct 25 '12 at 18:18
You can just write it out if you dont insist on a proof by induction. – Epsilon Oct 25 '12 at 22:13

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.

-
but don't I use the hypthesis for the subset that don't contain $a_{n+1}$? – user46021 Oct 25 '12 at 18:29
@psipi : Not that I can see, because you're not breaking that into a sum of two terms. – Michael Hardy Oct 25 '12 at 18:32
@psipi : Note that the induction hypothesis is not that $n \choose k$ counts the number of k-element subsets of $[n]$ (this is merely the definition of $n \choose k$) but, rather, that this is equivalent to your sum of smaller binomials. – AndrewG Oct 25 '12 at 18:35
@MichaelHardy Is there any possibility to prove by induction? – user46021 Oct 25 '12 at 18:46
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. – Michael Hardy Oct 25 '12 at 19:07

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\}$.

-

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.

-

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|$?

-
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. – Dilip Sarwate Oct 25 '12 at 18:30