# Proof by induction from Spivak's calculus ch 2- 3b

I was cracking my head over the following proof (by induction) from Spivak's calculus.

Givens: $\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$ and $n \ge k$

Task: Proof by induction that $\binom{n}{k}$ is always a natural number.

My approach was:

(1) For the base case I take $\binom{1}{k}$.

(2) I assume that $k = 1$ because $n \ge k$ giving $\binom{1}{1}=1$.

(3) I assume that $\binom{n}{k} \in\mathbb N$ holds and prove $\binom{n+1}{k}\in\mathbb N$.

(4) I apply the known formula $\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$.

(5) I know from (3) that $\binom{n}{k}\in\mathbb N$ holds.

(6) I do not know how to conclude that $\binom{n}{k-1} \in\mathbb N$

(7) I do not know how to conclude that the sum of two natural numbers is a natural number so that even if I knew that $\binom{n}{k-1} \in\mathbb N$ and take the assumption that $\binom{n}{k}\in\mathbb N$ I cannot conclude that $\binom{n+1}{k}\in\mathbb N$.

As you said, we will induct on $n$. But the claim will be, for a given $n$, that $\binom{n}{k}$ is an integer for any $k$. The base case will be $n=1$, and indeed $\binom{1}{0}=1,$ $\binom{1}{1}=1,$ and $\binom{1}{k}=0$ for $k\not=0,1$. Now assume the claim holds for some $n$. Then for any $k$ we have $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}.$$ Now our induction hypothesis assumes that both terms on the right hand side are integers, so their sum is an integer.
The trick is making the claim about all $k$, instead of a specific $k$.