I'm a high school graduate, who has started doing Spivak's Calculus, for fun. I was struggling a bit with a certain question on proving the above stated fact using Principle of Mathematic Indutction.
I came up with the following proof, but am unsure since it is very unlike previous PMI questions I've done.
$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k – 1}$$
For $n = 1$
$$\binom{1}{k} = \binom{1}{0}\space or \space \binom{1}{1} = 1$$
Therefore $\binom{n}{k}$ is a natural number when $n = 1$.
Assumption: $\binom{n}{k}$ is a natural number for all $k\in \{1, 2, \dots,n\}$
$$\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k – 1}$$.
$\binom{n}{k}$ is a natural number from the previous argument. The same applies to $\binom{n}{k – 1}$.
The remaining two possible values of $k$ are $n + 1$, $0$.
$$\binom{n+1}{0} = \binom{n+1}{n+1} = 1$$.
Therefore all the possible values of $\binom{n + 1}{k}$ are natural numbers.
Therefore, $\binom{n}{k}$ is always a natural number by induction.
Best Answer
Structurally your proof is correct(*). However what's missing is the definition of the binomial coefficient, that is what do $\binom{n}{k}$ mean? There's two ways to do that (perhaps more). One is to define it using the pascal triangle rule (recursive definition):
$$\binom{n}0 = \binom{n}{n} = 1$$ $$\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$$
With that definition your proof is straight forward as it relies on these identities.
Another way to define binomial coefficients is to define it as
$$\binom{n}{k} = {n!\over k! (n-k)!}$$
with this definition you must prove that the required identities hold, especially that $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$. However that is quite straight forward:
$$\binom{n}{k} + \binom{n}{k-1} = {n! \over k! (n-k)!} + {n!\over (k-1)!(n-k+1)!} \\ = {n! (n-k+1) \over k! (n-k+1)!} + {n!k\over k!(n-k+1)!} \\ = {n! (n-k+1) + n!k\over k! (n-k+1)!} \\= {(n+1)!\over k! (n-k+1)!} = \binom{n+1}{k}$$
(*) well almost, you have that it's allowed for $n=0$ in $\binom{n}{k}$, so you should have included the fact that $\binom{0}{0} = 1$ is a natural number.