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.

  • $\begingroup$ Prove that the factorial ratio satisfies a two-term recurrence relation with integer coefficients and integer initial value. $\endgroup$ – user02138 Oct 17 '12 at 3:26
  • 1
    $\begingroup$ I wonder if there isn't some way to make this into a product of binomial coefficients. $\endgroup$ – MJD Oct 17 '12 at 5:00
  • 5
    $\begingroup$ This was a 1972 IMO problem $\endgroup$ – Jemmy Oct 17 '12 at 5:40
  • $\begingroup$ Is there a way to interpret this expression as counting something? $\endgroup$ – pad Dec 17 '14 at 19:16
  • $\begingroup$ By induction is it possible ? $\endgroup$ – Maman Aug 30 '16 at 23:41

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)


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.