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 $.
Please help solving this. Please also check my exposition. Any comments on every aspect of my incomplete and possibly faulty proof are appreciated. Thanks in advance
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$.