1972 IMO Problems/Problem 3

Problem

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

Solution 1

Denote the given expression as $f(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)$ : $\begin{align*} f(m,n-1) &=\frac{(2m)!(2n-2)!}{m!(n-1)!(m+n-1)!}\\ &=\frac{(2m)!(2n)!(n-1)(m+n)}{m!n!(m+n)!(2n-1)(2n-2)}\\ &=f(m,n) \cdot \frac{(n-1)(m+n)}{(2n-1)(2n-2)}\\ &=f(m,n) \cdot \frac{m+n}{2(2n-1)} \end{align*}$ Second, let's look at $f(m+1,n-1)$ : $\begin{align*} 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) \cdot \frac{(2m+1)(2m+2)(n-1)}{(m+1)(2n-1)(2n-2)}\\ &=f(m,n) \cdot \frac{(2m+1)}{2n-1} \end{align*}$ Combining, $\begin{align*} 4f(m,n-1)-f(m+1,n-1) &=f(m,n)\cdot \Bigg(\frac{4(m+n)}{2(2n-1)}-\frac{2m+1}{2n-1}\Bigg)\\ &=f(m,n) \cdot \frac{2m+2n-2m-1}{2n-1}\\ &=f(m,n). \end{align*}$ Therefore, we have found the recurrence relation $f(m,n)=4f(m,n-1)-f(m+1,n-1).$

Note that $f(m,0)$ is just $\binom{2m}{m}$ , which is an integer for all $m \geq 0$ . Then $f(m,1)=4f(m,0)-f(m+1,0),$ so $f(m,1)$ is an integer, and therefore $f(m,2)=4f(m,1)-f(m+1,1)$ must be an integer, etc.

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

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

Solution 2

Let p be a prime, and n be an integer. Let $V_p(n)$ be the largest positive integer $k$ such that $p^k|n$

WTS: For all primes $p$ , $V_p((2m)!)+V_p((2n)!) \ge V_p(m!)+V_p(n!)+V_p((m+n)!)$

We know $V_p(x!)=\sum_{a=1}^{\infty} \left\lfloor{\frac{x}{p^a}}\right\rfloor$

Lemma 2.1: Let $a,b$ be real numbers. Then $\lfloor{2a}\rfloor+\lfloor{2b}\rfloor\ge\lfloor{a}\rfloor+\lfloor{b}\rfloor+\lfloor{a+b}\rfloor$

Proof of Lemma 2.1: Let $a_1=\lfloor{a}\rfloor$ and $b_1=\lfloor{b}\rfloor$

$\lfloor{2a}\rfloor+\lfloor{2b}\rfloor=2(a_1+b_1)+\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor$

On the other hand, $\lfloor{a}\rfloor+\lfloor{b}\rfloor+\lfloor{a+b}\rfloor=a_1+b_1+(a_1+b_1)+\lfloor\{2(a+b)\}\rfloor$

It is trivial that $\lfloor2\{a\}\rfloor+\lfloor2\{b\}\rfloor\ge\lfloor\{2(a+b)\}\rfloor$ (Triangle Inequality)

Apply Lemma 2.1 to the problem: and we are pretty much done.

Note: I am lazy, so this is only the most important part. I hope you can come up with the rest of the solution. This is my work, but perhaps someone have come up with this method before I did.

Remark about, and correction to Solution 2

The last step seems mistaken. For example [1.5]+[1.5]<[1.5+1.5]. Triangle inequality is about absolute value |x| not floor function [x]. Following is a rectified solution.

Lemma: [a+b]<=[a]+[b]+1, a,b>=0.

Proof: a<[a]+1, b<[b]+1, so a+b<[a]+[b]+2, [a+b]<=a+b<[a]+[b]+2, so [a+b]<=[a]+[b]+1.

Let (x,2x,…,nx)=n, p is any prime, V2(9!)=V2(1•2•3•4•5•6•7•8•9) =(2,4,6,8)+(4,8)+(8)=[9/2]+[9/4]+[9/8]=7.

Generalize it and we have, Vp(m!)=Vp(1•2•….•m)=[m/p]+[m/p^2]+…+[m/p^k], k=1~∞, or,

Vp(m!)=∑([m/p^k],k=1~∞) $\ \ \ \ (1)$ .

Obviously when p^k>m, k>=1, [m/p^k]=0.

Note the target statement is equivalent to:

for any prime p, Vp((2m)!(2n)!)>=Vp(m!n!(m+n)!), or,

Vp((2m)!)+Vp((2n)!)>=Vp(m!)+Vp(n!)+Vp(m+n)! $\ \ \ \ (2)$ .

Let m/p^k=a(k), n/p^k=b(k), k=1~∞. Combine (1), we note that (2) is equivalent to:

for any k in (1), [2a(k)]+[2b(k)]>=[a(k)]+[b(k)]+[a(k)+b(k)] $\ \ \ \ (3)$ .

For convenience of viewing, let a(k)=a, b(k)=b, a,b>=0, (3) is then rewritten as:

[2a]+[2b]>=[a]+[b]+[a+b] $\ \ \ \ (4)$ .

We prove it under different scenarios:

-If a<[a]+1/2, b<[b]+1/2, Then 2[a]<=[2a]<=2a<2[a]+1, [2a]=2[a], likewise, [2b]=2[b], so (4) is equivalent to [a]+[b]>=[a+b]. Per current condition, a+b<[a]+[b]+1, so [a+b]<[[a]+[b]+1]=[a]+[b]+1, also obviously [a+b]>=[a]+[b], so [a+b]=[a]+[b], proved;

-If a<[a]+1/2, b>=[b]+1/2, then [2a]=2[a], [2b]=2[b]+1, so (4) is equivalent to [a]+[b]+1>=[a+b], as per lemma, proved;

-If a>=[a]+1/2, b>=[b]+1/2, so [2a]=2[a]+1, [2b]=2[b]+1, so (4) is equivalent to [a]+[b]+2>=[a+b], as per lemma, proved;

Therefore (4) is proved, so is (2), as every step from (2) to (4) is reversible. Therefore (2m)!(2n)!/(m!n!(m+n)!) is an integer. Proof completed.

Remarks (added by pf02, April 2025)

1. The first solution has a few errors in the computation, but they cancel out, and the proof is essentially correct. Below I will give the corrections, to make the solution flawless.

2. As pointed out by a contributor, the second solution is incorrect. The correction given is good, but very sloppily written and hard to read (even after I edited the spacing, to make it legible). Below, I will repeat the argument in a simplified form, to make it easier to follow.

3. I will give a third solution below, inspired by the papers mentioned in the next paragraph.

4. The problem is a classical result, attributed to Eugene Catalan, who stated it in a paper published in 1874. The numbers $S(m, n) = \frac{(2m)!(2n)!}{m!n!(m+n)!}$ are sometimes called the super-Catalan numbers. (They are mentioned at the end of https://en.wikipedia.org/wiki/Catalan_number).

There are a few papers published about them. See for example the paper "The Super Catalan Numbers $S(m, m + s)$ for $s \le 3$ and Some Integer Factorial Ratios" by Xin Chen & Jane Wang (https://www-users.cse.umn.edu/~reiner/REU/ChenWang2012.pdf), and "Super Ballot Numbers" by Ira M. Gessel (especially section 6) (https://www.sciencedirect.com/science/article/pii/0747717192900342/pdf).

Corrected computations in Solution 1

We have

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

and

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

The rest of the proof is correct.

Simplified version of the correction to Solution 2

To prove that $S(m, n) = \frac{(2m)!(2n)!}{m!n!(m+n)!}$ is an integer, we have to prove that for any prime number $p$ , the exponent of the largest power of $p$ in $(2m)!(2n)!$ is larger than the exponent of the largest power of $p$ in $m!n!(m+n)!$ . (In fact, we have to consider only primes which satisfy $p \le m + n$ ).

The largest power of $p$ in $N$ ! is given by $\nu_p(N!) = \sum_{i=1}^{\infty} \left\lfloor\frac{N}{p^i}\right\rfloor$ . (The sum is a finite sum, since we have to consider only powers $i \le \lfloor\log_p N\rfloor.)$ This is easy to see, but it is a reasonably well known fact (see Legendre's Formula or https://en.wikipedia.org/wiki/Legendre's_formula.) Note that $\nu_p(M!N!) = \nu_p(M!) + \nu_p(N!)$ .

Thus, it is enough to prove that $\left\lfloor\frac{2m}{p^i}\right\rfloor + \left\lfloor\frac{2n}{p^i}\right\rfloor \ge \left\lfloor\frac{m}{p^i}\right\rfloor + \left\lfloor\frac{n}{p^i}\right\rfloor + \left\lfloor\frac{m + n}{p^i}\right\rfloor\ \ \ \ \ \ \ \ (1)$ .

Let $m = Q_1 \cdot p^i + R_1$ be the integer division of $m$ by $p^i$ (so $0 \le Q_1 < p^i$ ), and let $r_1 = \frac{Q_1}{p^i}$ . In other words, $r_1 = \frac{m}{p^i} - \left\lfloor\frac{m}{p^i}\right\rfloor$ . Note that $0 \le r_1 < 1$ . Similarly, obtain $r_2$ from the division of $n$ by $p^i$ .

Note that $\left\lfloor\frac{2m}{p^i}\right\rfloor = 2\left\lfloor\frac{m}{p^i}\right\rfloor$ or $\left\lfloor\frac{2m}{p^i}\right\rfloor = 2\left\lfloor\frac{m}{p^i}\right\rfloor + 1$ depending on whether $r_1 < \frac{1}{2}$ or $r_1 \ge \frac{1}{2}$ and similarly for $n$ and $r_2$ . Also $\left\lfloor\frac{m + n}{p^i}\right\rfloor = \left\lfloor\frac{m}{p^i}\right\rfloor + \left\lfloor\frac{n}{p^i}\right\rfloor$ or $\left\lfloor\frac{m + n}{p^i}\right\rfloor = \left\lfloor\frac{m}{p^i}\right\rfloor + \left\lfloor\frac{n}{p^i}\right\rfloor + 1$ depending on whether $r_1 + r_2 < 1$ or $r_1 + r_2 \ge 1$ .

We have the following cases:

1. If $r_1 < \frac{1}{2}$ and $r_2 < \frac{1}{2}$ then we have equality in (1).

2. If $r_1 \ge \frac{1}{2}, r_2 < \frac{1}{2}$ , and $r_1 + r_2 < 1$ then after cancelling terms, the left hand side in (1) becomes 1, and the right hand side becomes 0.

3. If $r_1 \ge \frac{1}{2}, r_2 < \frac{1}{2}$ , and $r_1 + r_2 \ge 1$ then we have equality in (1).

4, 5. The two cases when $r_1 < \frac{1}{2}, r_2 \ge \frac{1}{2}$ are similar to cases 2 and 3.

6. If $r_1 \ge \frac{1}{2}, r_2 \ge \frac{1}{2}$ , then after cancelling terms, the left hand side in (1) becomes 2, and the right hand side becomes 1.

The above shows that (1) is always true, which proves the problem.

Solution 3

This solution uses the fact that ${n \choose k} = \frac{n!}{k!(n - k)!}, k = 0, \dots n$ are the coefficients of the powers of $x$ in the expansion of $(1 + x)^n$ (see Binomial Theorem or https://en.wikipedia.org/wiki/Binomial_coefficient). Of course these coefficients, hence these expressions in $n, k$ are integers.

Without loss of generality, we can assume $m \le n$ . We will use the identity

$S(m, n) = \frac{(2m)!(2n)!}{m!n!(m+n)!} = (-1)^m \sum_{k=0}^{k=2m} (-1)^k {2m \choose k} {2n \choose m + n - k}$ .

This identity is attributed to K. von Szily (1894). Note that we could take the sum over all integers, using the convention that ${n \choose k} = 0$ when $k < 0$ or $k > n$ .

The fact that $S(m, n)$ is integer follows immediately from this identity because the right hand side is integer.

Thus, we just need to prove this identity.

Start with $(1 - x^2)^{m + n} = (1 + x)^{m + n} (1 - x)^{m + n}$ . Expand both sides and look at the coefficient of $x^{2m}$ in both expansions. Equate the two expressions giving the coefficient of $x^{2m}$ in the two sides. We get

$(-1)^m {m + n \choose m} = \sum_{k=0}^{2m} {m + n \choose k} \cdot (-1)^{2m - k} {m + n \choose 2m - k}$ .

Write out the binomial coefficients in terms of factorials, and multiply both sides by $(-1)^m \frac{(2m)!(2n)!}{[(m + n)!]^2}$ . We get

$\frac{(m + n)!}{m!n!} \cdot \frac{(2m)!(2n)!}{[(m + n)!]^2} = (-1)^m \sum_{k=0}^{2m} (-1)^k \frac{(m + n)!}{k!(m + n - k)!} \cdot \frac{(m + n)!}{(2m - k)!(n - m + k)!} \cdot \frac{(2m)!(2n)!}{[(m + n)!]^2}$

Simplifying and rearranging factors, we get

$\frac{(2m)!(2n)!}{m!n!(m + n)!} = (-1)^m \sum_{k=0}^{2m} (-1)^k \frac{(2m)!}{k!(2m - k)!} \cdot \frac{(2n)!}{(n + m - k)!(n - m + k)!} = (-1)^m \sum_{k=0}^{2m} (-1)^k {2m \choose k} {2n \choose n + m - k}$

This finishes the problem.

1972 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search