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