Prove by Induction that $\binom{n}{k}$ is always a natural number. I have come up with the following proof.
Base Case: If n = 1, then k = 1 because n $\geq$ k , $\forall$n,k $\in$ $\mathbb{N}$.
Thus, $\binom{1}{1}$ = $\frac{1!}{1!(1-1)!} = 1 \in \mathbb{N}$.
Inductive Hypothesis: Assume that $\binom{m}{k} \in \mathbb{N}$ for some $m \in \mathbb{N}$.
Inductive Step: We are given that $\binom{m+1}{k} = \binom{m}{k-1} + \binom{m}{k}$. By assumption, we know that $\binom{m}{k} \in \mathbb{N}$, so as a result we must prove that $\binom{m}{k-1} \in \mathbb{N}$. Because the natural numbers are closed under addition, the sum of the two terms will also result in a natural number.
Hence, a bit of algebra yields $\binom{m}{k-1} = \frac{k}{m-k+1} \times \binom{m}{k}$. This is where I’m stuck. I need to show that $\frac{k}{m-k+1} \in \mathbb{N}$. From this, I can then claim that the product is then a natural number because the natural numbers are closed under multiplication.
Αny help would be appreciated! Thank you.

Hint: Here’s a better inductive assumption: Assume that for some $m$ (the induction variable) the binomial coefficient $\begin{pmatrix}m\\k\end{pmatrix}$ is a natural number for every $0 \leq k \leq m$.
