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

-
Prove that the factorial ratio satisfies a two-term recurrence relation with integer coefficients and integer initial value. –  user02138 Oct 17 '12 at 3:26
I wonder if there isn't some way to make this into a product of binomial coefficients. –  MJD Oct 17 '12 at 5:00
This was a 1972 IMO problem –  Jeremy Oct 17 '12 at 5:40

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

-