# Prove that $\ell!(n-\ell)! \mid n!$ using double induction

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?

• You can't show that, since it would show that it would be true for $l>n$. You first should show that $P(n,n)$ holds for all $n$, and then prove that for all $l>0$, $P(n,l)$ implies $P(n,l-1)$. Sep 8, 2021 at 17:22
• Following the above comment, use Pascal's formula to show that all binomial coefficients are integers if the boundary (in the triangle up to some height) are. It's not as pretty as interpreting the coefficients combinatorially, but it is alright, I guess!
– Pedro
Sep 8, 2021 at 17:28

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 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.