Using original definition of n choose k, prove an equivalency I'm working on the following problem:
Define $n \choose k$ to be the number of $k$-element subsets of the set $\{1,\cdots ,n\}$. Prove from this definition that $n \choose k$ = ${n-1} \choose k$ + ${n-1} \choose {k-1}$.
There's a hint in my book that says to consider the case where my particular $k$-element subset contains $n$ or not.
I've been working on this for about an hour, and I haven't gotten very far. First I wrote out what all of the combinations involved really mean according to the definition, to try to get a feel for what we're doing.
I've tried defining the specific sets of $k$-element subsets of each combination and playing with their magnitudes, but haven't gotten anywhere. I tried to let $K$ be a specific $k$-element subset of $\{1,\cdots,n\}$ in order to try to use the hint, but I don't see what proving something about $K$ actually accomplishes when we're trying to count them. I can see that $K$ can't be a subset of the other two combinations if $n \in K$, and if $n \notin K$, $K$ should be in the set containing $k$-element subsets of ${1,\cdots,n-1}, but I don't really see where that gets me.
If someone could give me a push in the right direction, that would be great. I'm not looking for an answer because I understand that the only real way to learn this stuff is to figure it out on your own. Thanks!
 A: Since $n \choose k$ represents the number of k-element subsets of a set with n elements, you can think of forming a k-element subset by breaking it up into two cases:
1) The case where the subset contains the element n, in which case you have to 
   choose k-1 elements from the ones remaining.
2) The case where the subset does not contain the element n, in which case you have to choose k elements from the ones remaining.
A: The expression on the left counts the number of $k$-element subsets one can select from a set of $n$ elements. Pick a specific element, $X$, from $\{1, \dots, n\}$. Any $k$-element subset either contains $X$ or it doesn't.
Look at the $k$-element sets that contain $x$. How many of them are there? Well, you've already selected $X$ so you have to pick the remaining $k-1$ elements from the $n-1$ elements left in your big set. In other words, you will have
$$
\binom{n-1}{k-1}
$$ 
subsets which contain $X$.
Now do the same thing with the $k$-element subsets that don't contain $X$.
A: Since you don't want answers, and just hints, I will leave this here:
Given a $k$-element subset $K$, you said that if $n \notin K$, then $K$ should be is the group of sets that are $k$-element subsets of $\{1,\ldots,n-1\}$. This is a key point. You have isolated one group of sets. How many of such sets are there? Do you see one of the terms of the answer pop out?
Now what is left over? What if $n \in K$? How many $k$-element subsets have an $n$ in it? There are many possible hints from here, looking at the form of the answer,  isolating $n$ and staring at $K - n$, for instance...
