Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer.

I'm not familiar to factorial and I don't have much idea, can someone show me how to prove this? Thank you.

Solution 1:

Consider a prime $p$. The highest power of $p$ dividing the numerator is $$\alpha_{Nr} = \left(\left \lfloor \dfrac{2m}{p}\right \rfloor + \left \lfloor \dfrac{2m}{p^2}\right \rfloor + \left \lfloor \dfrac{2m}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{2n}{p}\right \rfloor + \left \lfloor \dfrac{2n}{p^2}\right \rfloor + \left \lfloor \dfrac{2n}{p^3}\right \rfloor + \cdots \right)$$

The highest power $p$ dividing the denominator is $$\alpha_{Dr} = \left(\left \lfloor \dfrac{m}{p}\right \rfloor + \left \lfloor \dfrac{m}{p^2}\right \rfloor + \left \lfloor \dfrac{m}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{n}{p}\right \rfloor + \left \lfloor \dfrac{n}{p^2}\right \rfloor + \left \lfloor \dfrac{n}{p^3}\right \rfloor + \cdots \right) + \left(\left \lfloor \dfrac{m+n}{p}\right \rfloor + \left \lfloor \dfrac{m+n}{p^2}\right \rfloor + \left \lfloor \dfrac{m+n}{p^3}\right \rfloor + \cdots \right)$$

You may want to look at this post that discusses the highest power of a prime dividing $N!$.

The goal now is to show that $\alpha_{Nr} > \alpha_{Dr}$. If we prove that $$\lfloor 2x \rfloor + \lfloor 2y \rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$ we are then done. Can you now prove this one?

We have $x = \lfloor x \rfloor + \{x \}$ and $y = \lfloor y \rfloor + \{y \}$.

We will consider 4 cases.

Case $1$: $\{x\} <1/2$, $\{y\} <1/2$. Then $\lfloor 2x \rfloor = 2 \lfloor x \rfloor$ and $\lfloor 2y \rfloor = 2 \lfloor y \rfloor$ and $\lfloor x + y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor$. Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Case $2$: $\{x\} <1/2$, $\{y\} >1/2$ or $\{x\} >1/2$, $\{y\} <1/2$. Then $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = 2 \lfloor x \rfloor + 2 \lfloor y \rfloor + 1$$ Further, $$\lfloor x+y \rfloor \leq \lfloor x \rfloor + \lfloor y \rfloor + 1$$ Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Case $3$: $\{x\} >1/2$, $\{y\} >1/2$. Then $$\lfloor 2x \rfloor + \lfloor 2y \rfloor = 2 \lfloor x \rfloor + 2 \lfloor y \rfloor + 2$$ Further, $$\lfloor x+y \rfloor = \lfloor x \rfloor + \lfloor y \rfloor + 1$$ Hence, we have $$\lfloor 2x \rfloor + \lfloor 2y \rfloor > \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor$$

Solution 2:

Denote $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ by $S(n,m)$. It satisfies relation $S(n+1,m)+S(n,m+1)=4S(n,m)$ (cf. Pascal's triangle) — or, equivalently, $S(n+1,m)=4S(n,m)-S(n,m+1)$. Since $S(0,m)=\binom{2m}m$ is an integer, this relation implies that all $S(n,m)$ are integers.

Ref.: I. Gessel. Super Ballot Numbers (via MO)