# Understanding a proof of the fact that $\binom{n}{k}$ is always a natural number.

Original source of question and solution. Question is on the left, answer is on the right.

Question: Notice that all the numbers in Pascal's triangle are natural numbers. Use part (a) to prove by induction that $\binom{n}{k}$ is always a natural number. (Your entire proof by induction will, in a sense, be summed up in a glance by Pascal's triangle.)

Solution: Clearly $\binom{1}{1}$ is a natural number. Suppose that $\binom{n}{p}$ is a natural number for all $p \leq n$. Since

$$\binom{n+1}{p} = \binom{n}{p-1} + \binom{n}{p},\qquad \text{for}\ p \leq n,$$

it follows that $\binom{n+1}{p}$ is a natural number for all $p \leq n$, while $\binom{n+1}{n+1}$ is also a natural number. So $\binom{n+1}{p}$ is a natural number for all $p \leq n + 1$.

I tried to prove it by doing $C(n + 1, k) - C(n, k -1)$ and substituting that for $C(n, k)$. I thought everything would sort of end up equaling $\frac{n!}{k!(n-k)!}$. Thinking about it, I'm not sure why I thought that would prove it to be a natural number. I don't really know how to start. I think I need to prove that $n!$ is divisible by $k!(n-k)!$ but I have no idea how to show that. Seeing as how I already looked at the answer, I would really appreciate an explanation of the answer.

Thanks.

Sorry if the question is vague or whatever, you can fix it if you like.

EDIT: I understand what I did not before. Closure under addition says that if I add two natural number to each other, I get a natural number. So I need to prove that $C(n + 1, k)$ and $C(n, k - 1)$ are natural numbers.

-
The proof depends on the fact that sums of natural numbers are natural numbers. –  Tunococ Oct 8 '13 at 1:08
@Tunococ But I don't understand how I would prove n! and k! are natural numbers? –  Kat Oct 8 '13 at 1:12
What do you mean "I don't really know how to start"? Isn't the solution in the image? –  Michael Albanese Oct 8 '13 at 1:14
I don't think you need that for this problem. Evaluating the base case manually would be enough. –  Tunococ Oct 8 '13 at 1:15
@MichaelAlbanese It is, but I don't understand the solution. –  Kat Oct 8 '13 at 1:34

The solution is by induction. First, establish the base case. Clearly $${1 \choose 1} = \frac{1!}{1!(1-1)!} = \frac{1!}{1!0!} = \frac{1}{1\times 1} = 1$$ is a natural number. Now the inductive step, suppose ${n \choose p}$ is a natural number for all $0 \leq p \leq n$ (we are assuming that every entry the first $n+1$ rows of Pascal's triangle are natural numbers).
For all $0 \leq p \leq n+1$ we have Pascal's rule $${n+1 \choose p} = {n\choose p-1}+{n\choose p}.$$ By the inductive step, both numbers on the right hand side are natural numbers, so ${n+1\choose p}$ is a natural number for $0 \leq p \leq n+1$ (that is, all the entries in the $(n+2)^{\text{nd}}$ row are natural numbers). Note, the proof in the link treats the case $p = n+1$ separately but this isn't necessary as ${n \choose p} = 0$ for $p > n$.
Added Later: The base case here is the second row of Pascal's triangle. It would be better to start with the first row which is ${0\choose 0} = 1$. The reason why knowing ${1 \choose 1} = 1$ is enough to show that every entry in the second row of Pascal's triangle is a natural number is that there is only one other entry, ${1 \choose 0}$, which is $1$.
They are natural numbers by the inductive step. Are you familiar with induction? I wrote $0 \leq p \leq n$ because ${n \choose p} = 0$ for $p$ outside this range. Note ${n \choose p}$ for $0 \leq p \leq n$ are the $n+1$ entries in the $(n+1)^{\text{st}}$ row of Pascal's triangle. –  Michael Albanese Oct 8 '13 at 2:08
We are doing induction on the row of Pascal's triangle (that is $n$). We prove every element of the first row is a natural number (that's the base case), then we assume every element of the $(n+1)^{\text{st}}$ row is a natural number (the inductive step), and use that to prove every element of the $(n+2)^{\text{nd}}$ row is a natural number. The inequality refers to the elements within a given row. The elements of the $(n+2)^{\text{nd}}$ row, from left to right are ${n+1\choose 0}, {n+1\choose, 1}, \dots, {n+1\choose n}, {n+1\choose n+1}$. Instead of having to check that each of these is a ... –  Michael Albanese Oct 8 '13 at 2:23
... natural number individually, we can actually show that ${n+1\choose p}$ is a natural number for any choice of $p$ between $0$ and $n+1$ (that is, any entry in the row). –  Michael Albanese Oct 8 '13 at 2:25