IMO 1972 · Problem 3

Let \(m\) and \(n\) be arbitrary non-negative integers. Prove that \[ \frac{(2m)!(2n)!}{m!n!(m+n)!} \] is an integer. (\(0! = 1\).)

Official text of the problem. Official problem paper (PDF)

Solution

Write \[ S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}. \] For all non-negative integers \(m,n\), the factorial definition gives \[ S(m+1,n)=\frac{2(2m+1)}{m+n+1}S(m,n), \qquad S(m,n+1)=\frac{2(2n+1)}{m+n+1}S(m,n). \] Adding these equalities yields \[ S(m+1,n)+S(m,n+1)=4S(m,n). \]

We now prove by induction on \(n\) that \(S(m,n)\) is an integer for every non-negative integer \(m\).

For \(n=0\), \[ S(m,0)=\frac{(2m)!}{m!m!}=\binom{2m}{m}, \] which is an integer because it counts the \(m\)-element subsets of a set with \(2m\) elements. This also holds when \(m=0\).

Suppose the assertion holds for a fixed \(n\) and every non-negative integer \(m\). Then \[ S(m,n+1)=4S(m,n)-S(m+1,n) \] is an integer for every such \(m\), since both terms on the right are integers by the induction hypothesis.

Thus the required expression is an integer for all non-negative integers \(m,n\). \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).