Spivak's Calculus: Proofs concerning Pascal's Triangle Problem 3 of Chapter 2 in Spivak's Calculus poses 5 problems associated with Pascal's Triangle. The first of these asks you to prove that $\binom{n+1}{k}$ = $\binom{n}{k-1} + \binom{n}{k}$ which was fairly straightforward.
The second task was to prove by induction that $\binom{n}{k}$ is always a natural number. For this, I took the recursion approach: given the demonstration of the equality above, any $\binom{n}{k}$ can be decomposed into $\binom{n-1}{k-1} + \binom{n-1}{k}$ and so on, with each value decomposing until every binomial reaches either an $n$ or $k$ value of $0$, at which point they evaluate to 1 and can be summed. $1$ is a natural number, so the sum of any number of $1$s must therefore be a natural number. This proof seems to me as though it lacks formality, but I think the logic is appropriate.
The third task, however, I am simply unsure what to make of. It reads: "Give another proof that $\binom{n}{k}$ is a natural number by showing that $\binom{n}{k}$ is the number of sets of exactly $k$ integers each chosen from $1, \cdots,n$." The word induction is not used in the prompt, and I can see that this appears to be true across the first few rows of the triangle, but how one would rigorously prove something like this, I do not know. Additionally, having proven that this is true, is the link from that to $\binom{n}{k}$ always being a natural number just the fact that you cannot have partial or negative sets, and therefore it must be a natural number?

For convenience, let $S_n = \{x_1, x_2, x_3, \dots, x_n\}$ represent a set of $n$ distinct objects. 
Lets use $_nC_k$ to represent the number of ways of selecting $k$ objects from $S_n$.
So what does $_{n+1}C_k$ look like?
An element of such a selection will either include the object $x_{n+1}$ or it will not. We already know that there are $_nC_k$ ways to choose $k$ objects from the objects $x_1, x_2, \dots, x_n$. So how do we count the number of ways to select $k$ objects that contain $x_{n+1}$. Easy; we select $k-1$ objects from $S_n$ {there are $_nC_{k-1}$ such ways} and then add $x_{n+1}$ to the collection.
It follows that $_nC_{k-1} + _nC_k = _{n+1}C_k$.
