TITLE: Prove that $\ell!(n-\ell)! \mid n!$ using double induction
QUESTION [3 upvotes]: I want to show that $\ell!(n-\ell)! \mid n!$ (where $\mid$ denotes divides) for any $(n,\ell)\in (\mathbb{N}_0)^2$ with $\ell \leq n$ by double induction. This will ultimately then be a proof of the fact the binomial coefficients are integer valued.
Calling this claim $P(n,\ell)$, I have shown the basis $P(0,0)$ is true as well as $P(n,0) \Rightarrow P(n+1,0)$. This was not too difficult. What remains is showing $P(n,\ell) \Rightarrow P(n,\ell+1)$ which is a bit more tricky. I have tried several division results but haven't come across any significant progress. Can anyone help me complete the proof?

REPLY [2 votes]: I wrote this proof out, but then rereading it I realized I didn't actually prove it by induction, and just proved it directly... anyways, I'll leave it here but note that everything past the $**$ can be taken on its own as an enclosed proof.

Suppose that
$$k_1l!(n-l)!=n!$$
for some $l<n$ and $k_1\in\mathbb{N}$ (note the strictly less than here). Then
$$n!=k_1[1\cdot 2\cdot 3\cdot ... \cdot l][1\cdot 2\cdot 3\cdot ...\cdot (n-(l+1))\cdot (n-l)]$$
Now consider the equation
$$k_1(n-l)=k_2(l+1)$$
which is certainly true for some $k_2\in\mathbb{Q}$. To complete the proof, it is sufficient to show that $k_2\in\mathbb{N}$ as we would then have
$$n!=k_2(l+1)[1\cdot 2\cdot 3\cdot ... \cdot l][1\cdot 2\cdot 3\cdot ...\cdot (n-(l+1))]$$
$$=k_2[1\cdot 2\cdot 3\cdot ... \cdot l\cdot (l+1)][1\cdot 2\cdot 3\cdot ...\cdot (n-(l+1))]=k_2 (l+1)! (n-(l+1))!$$
as desired. With this in mind, we write
$$k_2=\frac{n!(n-l)}{l!(n-l)!(l+1)}$$
Note that we are not assuming $k_2$ is an integer here, but it is certainly true that it equals the above expression. Simplifying, we have
$$=\frac{n!}{l!(n-(l+1))!(l+1)}=\frac{n\cdot (n-1)\cdot (n-2)\cdot ... \cdot (n-l)}{1\cdot 2\cdot 3\cdot ... \cdot  (l+1)}$$

$**$ Here all that is required is to note that
$$\binom{n}{l+1}=k_2=\frac{n\cdot (n-1)\cdot (n-2)\cdot ... \cdot (n-l)}{1\cdot 2\cdot 3\cdot ... \cdot  (l+1)}$$
and the rest follows.

Now, note that the numerator is $l+1$ consecutive integers being multiplied and the denominator is $l+1$ consecutive integers being multiplied. Further, the denominator starts at $1$ while the numerator starts at $n-l$. These facts are enough to prove the claim. To demonstrate this, define
$$R(p^m,S)=|\{a\in S: p^m|a\text{ but }p^{m+1}\not| a\}|$$
for some set $S$, $m\in\mathbb{N}$, and $p$ prime. Note that this function is $0$ for all but a finite number of $m$. It is obvious that for any $p$ and $m$ we have
$$R(p^m,\{1,2,...,l+1\})=\left\lfloor \frac{l+1}{p^m}\right\rfloor$$
(which corresponds to the denominator of $k_2$). For the numerator, we have that
$$R(p^m,\{n-l,n-l+1,...,n\})\geq\left\lfloor \frac{l+1}{p^m}\right\rfloor$$
The greater than or equal to in this case occurs since $n-l$ might not be congruent to $1$ modulo $p^m$, and therefore possibly adding more numbers divisible by $p^m$ to the count. In fact, we don't really care whether or not it is greater than or equal, as equality is enough for our purposes. Reaching near the end of our proof, define $N_p$ as the highest power of a prime $p$ which divides the numerator of $k_2$ and define $D_p$ as the highest power of a prime $p$ which divides the denominator of $k_2$. For all primes $p$, we have
$$N_p=\sum_{i=0}^\infty R(p^i,\{n-l,n-l+1,...,n\})\geq\sum_{i=0}^\infty \left\lfloor \frac{l+1}{p^i}\right\rfloor$$
$$=\sum_{i=0}^\infty R(p^m,\{1,2,...,l+1\})=D_p$$
The greater than or equal distributes over the infinite sum as all but a finite number of the terms are $0$. We conclude that for all prime numbers we have $N_p\geq D_p$ and therefore the denominator of $k_2$ divides the numerator of $k_2$. Of course, this implies $k_2$ is an integer and we are done.
{"set_name": "stack_exchange", "score": 3, "question_id": 4245296}