1972 IMO Problems/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$ .)

Solution

Let $f(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}$ . We intend to show that $f(m,n)$ is integral for all $m,n \geq 0$ . To start, we would like to find a recurrence relation for $f(m,n)$ .

First, let's look at $f(m,n-1)$ :

$f(m,n-1)=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!}=\frac{(2m)!(2n)!(n-1)(m+n-1)}{m!n!(m+n)!(2n-1)(2n-2)}=f(m,n) \frac{(n-1)(m+n-1)}{(2n-1)(2n-2)}=f(m,n) \frac{m+n-1}{2(2n-1)}$

Second, let's look at $f(m+1,n-1)$ :

$f(m+1,n-1)=\frac{(2m+2)!(2n-2)!}{(m+1)!(n-1)!(m+n)!}=\frac{(2m)!(2n)!(2m+1)(2m+2)(n-1)}{m!n!(m+n)!(m+1)(2n-1)(2n-2)}=f(m,n) \frac{(2m+1)(2m+2)(n-1)}{(m+1)(2n-1)(2n-2)}=f(m,n) \frac{(2m+1)}{2n-1}$

Combining,

$4f(m,n-1)-f(m+1,n-1)=f(m,n) (\frac{4(m+n-1)}{2(2n-1)}-\frac{2m+1}{2n-1})=f(m,n) \frac{2m+2n-2-2m+1}{2n-1}=f(m,n)$ .

Therefore, we have found the recurrence relation $f(m,n)=4f(m,n-1)-f(m+1,n-1)$ .

We can see that $f(m,0)=\frac{(2m)!}{m!m!}$ is integral because the RHS is just $_{2m} C _m$ , which we know to be integral for all $m \geq 0$ .

So, $f(m,1)=4f(m,0)-f(m+1,0)$ must be integral, and then $f(m,2)=4f(m,1)-f(m+1,1)$ must be integral, etc.

By induction, $f(m,n)$ is integral for all $m,n \geq 0$ .

Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html

Solution 2

An alternative solution is nested induction in n and m. As induction start we have the case $n = 0$ . In that case $m!n!(m+n)! = (m!)^2$ and $(2m)!(2n)! = (2m)!$ .

With induction in $m$ we prove the induction start for $n = 0$ which states that

$(2m)!$ is a multiple of $(m!)^2$ for all natural numbers $m$ (including 0) (Assertion 1):

For $m = 0$ (induction start) we have $(2m)! = 1 = (m!)^2$ . Hence, we can assume that Assertion 1 holds for $m - 1$ and $m > 0$ : That means that $(2m-2)!$ is a multiple of $((m-1)!)^2$ . Division by $(m-1)!$ leads to the result that $X:= (m-1)! = 1 \cdot 2 \cdot \ldots (m-1)$ is a divisor of $M := m \cdot \ldots \cdot (2m-2)$ and thus $X' := mX = 1 \cdot 2 \cdot \ldots m$ is a divisor of $M' := 2m(2m-1)M = m \cdot \ldots \cdot 2m$ . And so $(m!)^2 = m!X'$ is a divisor of $m!M' = (2m)!$ , which is Assertion 1.

Hence, for $n = 0$ as induction start in $n$ the statement holds for all $m$ . So we assume that the statement also holds for all natural numbers $n - 1$ , where $n > 0$ , and all natural numbers $m$ (including 0), which means that we assume that $m!(n-1)!(m+n-1)!$ divides $(2m)!(2n-2)!$ for all $m$ . Division by $m!(n-1)!$ leads to the result that $X:= (m+n-1)! = 1 \cdot 2 \cdot \ldots (m + n - 1)$ is a divisor of $M := [(m + 1) \cdot \ldots \cdot 2m] \cdot [n \cdot \ldots \cdot (2n-2)]$ and thus $X' := m!nX = m!(m + n)!$ is a divisor of $M' := m!2n(2n-1)M$ . And so $n!m!(n+m)! = n!X'$ is a divisor of $n!M' = (2m)!(2n)!$ , which was to prove.

Agentmmk (talk) 16:43, 27 October 2015 (EDT)

Page

Toolbox

Search

1972 IMO Problems/Problem 3

Solution

Solution 2