Define $n!$ for $n ∈ \mathbb{N}_{0}$ by $0! = 1, (n + 1)! = n! (n + 1)$. Prove by induction on $n$ that $(n – r)!r!$ divides $n!$ for all $0 ≤ r ≤ n$.
Here's my attempt at the proof:
Let $S = \{n ∈ \mathbb{N}_{0}; (n-r)!r! \mid n! \}$.
Base case, $n = 0$:
$n! = q((n-r)!r!)$
$0! = q((0-0)!0!)$ ($r$ being 0 is the only possibility when $n = 0$)
$0! = q\cdot1$
$ q = 1 $ (which shows that $0 ∈ S$)
Induction step: Let's assume the proposition holds for all $k ∈ \mathbb{N}_{0}$ up to and including $n$. We have to show that for all $r ∈ \mathbb{N}_{0}; 0 ≤ r ≤ n + 1$ the following holds: $(n + 1)! = p(((n+1)-r)!r!)$ , where $p ∈ \mathbb{N}_{0}$.
Hence,
$n!\cdot(n+1) = q((n-r)!r!) \cdot (n+1)$
$(n+1)! = q((n-r)!r!) \cdot (n+1)$
$(n+1)! = q(n-r)!r! \cdot ((n-r+1)+r)= r!(n-r+1)!\cdot (q+qr(n-r)!\frac{1}{n-r+1})$
$(n+1)! = r!(n-r+1)!\cdot \frac{q\cdot(n+1)}{(n+1)-r}=r!(n-r+1)!\cdot \underbrace{\frac{q}{1-\frac{r}{n+1}}}_{p}$
I have a feeling that something went wrong somewhere, since I don't know how to prove that $\frac{q}{1-\frac{r}{n+1}}$ is indeed an element of $\mathbb{N}_{0}$ for all $0 ≤ r ≤ n + 1$, because there is a a problem with $r = n + 1$ due to division by $0$. Also it seems that there is a simpler way to a proof.
You can prove Pascal's identity completely algebraically or combinatorically if you please to avoid using two inductive proofs in a row.
To finish your prove this statement, it suffices to show that $\binom{n}{r}$ is always an integer.
We use Pascal's identity, given by $$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$ with no restrictions on the size of $n$ or $r$, since if $r>n$, we have $\binom{n}{r}=0$ and the identity holds.
So let $n=0$. Then $\binom{0}{0}=1\in\mathbb{N}$ so we are done with the base case.
Now suppose that $\binom{n}{r}$ is an integer for some $n\in\mathbb{N}$ and for every $r$ with $0\leq r\leq n$.
Let $1\leq r\leq n+1$. The case when $r=0$ holds. Then,
$$\binom{n+1}{r}=\binom{n}{r}+\binom{n}{r-1}$$ By hypothesis, $\binom{n}{r}$ is an integer if $r<n+1$ and is $0$ if $r=n+1$. Also by hypothesis, $\binom{n}{r-1}$ is an integer, so their sum is an integer. This completes the proof by induction.
You could also just give a combinatorial argument for this as well, where $\binom{n}{r}$ is the number of $r$ element subsets of an $n$ element set.
The argument of this goes as follows:
Suppose we want to select a $k$ element string from an $n$ element set. There are $n$ ways to choose the first element, $n-1$ ways to choose the second element, $n-2$ ways to choose the third element, and continuing in this way, there are $n-(k-1)$ ways to choose the $k$th element of the string.
Then $$n(n-1)(n-2)\cdots(n-(k-1))=\frac{n!}{(n-k)!}$$ is the number of strings of length $k$. Since the ordering of the elements in a subset does not matter, then we must account for that. We notice that each $k$ element subset occurs $k!$ times among these strings, as the elements in the strings can be permuted in $k!$ different ways. Therefore the number of $k$ element subsets of an $n$ element set is given by $$\binom{n}{k}=\frac{n!}{(n-k)!\cdot k!}$$