TITLE: Proof that $\binom{ n}{k} \in \mathbb N$
QUESTION [2 upvotes]: This problem is from Spivak. 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, \ldots,n$.
I went ahead and argued that since, by the multiplication principle, the number of ways to choose $k$ integers from $n$ with order is $n(n-1)(n-2)\cdots(n-k+1)$ or $\frac{n!}{(n-k)!}$ and the number of ways to arrange any $k$ integers is $k!$, that the number of ways to choose $k$ integers from $1,\cdots,n$ without order has to be $\frac{n!}{k!(n-k)!}=\binom{n}{k}$. Somehow though, in a chapter on induction, I doubt this is what Spivak was looking for. 
I just don't know how to rigorously define the idea of "the number of subsets of $1, \ldots, n$ with cardinality $k$."

REPLY [0 votes]: This is the given answer to that question:

There are $n(n-1)...(n-k+1)$ $k$-tuples of distinct integers each chosen from $1,...,n$ since the first can be picked in $n$ ways, the next in $n-1$ ways, etc. Now each set of exactly $k$ integers can be arranged in $k!$ $k$-tuples, so there are $n(n-1)...(n-k+1)/(k!)= {n\choose k}$

Hopefully that elucidates it a little; I sympathise with you about doing Spivak's problems and sometimes not really knowing how he intended you to answer it. I remember this problem and my answer looked nothing like the one above.

REPLY [0 votes]: I don't know if this is exaclty what are you asking: 
Define the binomial coefficient $\binom {n} {k}$ as follows: the number of subsets of ordered $k$ in the set $\{1,\ldots,n\}$.
Claim:  For every integer $n$ and every $k\le n$ we have $\binom {n} {k}=\binom {n-1} {k}+\binom {n-1} {k-1}$
Proof: Let $S$ be a subset of $\{1,\ldots,n\}$ of $k$ elements. Then either $n\in S$ or $n\notin S$. If $n\notin S$, so $S \subset \{1,\ldots,n-1\}$ and by definition there are $\binom {n-1} {k}$ of these subsets. Suppose that $n\in S$, define $S' = S \setminus\{n\}$. Then $S'$ is a subset of $\{1,\ldots,n-1\}$ and so there are $\binom {n-1} {k-1}$ such sets $S'$. Hence there are $\binom {n-1} {k-1}$ subsets of ordered $k$ which contain $n$.  Thus this give us a total of $\binom {n-1} {k}+\binom {n-1} {k-1}$ sets of ordered $k$ in general, i.e., $\binom {n} {k}=\binom {n-1} {k}+\binom {n-1} {k-1}$
Proposition:$\binom {n} {k}= \frac{n!}{k! (n-k)!}$
Proof: Let $P(n)$ be the statement: "$\binom {n} {k}= \frac{n!}{k! (n-k)!}$ is true for all $k\le n$". Suppose that $P(n-1)$ is true, so 
$$\binom {n-1} {k}=\frac{(n-1)!}{k!(n-1-k)!}\;\; \text{and }\;\; \binom {n-1} {k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}$$
Thus by the claim  
\begin{align}\binom {n} {k}=\binom {n-1} {k}+\binom {n-1} {k-1}=\frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!}\\= \frac{n!}{k! (n-k)!} \end{align}
So this definition of binomial coefficient agrees with the other, and I suppose that you have already proven that $\frac{n!}{k! (n-k)!}$ is a natural number.
{"set_name": "stack_exchange", "score": 2, "question_id": 716278}