Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1972 IMO Problems/Problem 3"
(→‎Solution)
Line 4: Line 4:
  
 
== Solution ==
 
== Solution ==
 +
 +
Let <math>f(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}</math>. We intend to show that <math>f(m,n)</math> is integral for all <math>m,n \geq 0</math>. To start, we would like to find a recurrence relation for <math>f(m,n)</math>.
 +
 +
First, let's look at <math>f(m,n-1)</math>:
 +
 +
<math>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)}</math>
 +
 +
Second, let's look at <math>f(m+1,n-1)</math>:
 +
 +
<math>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}</math>
 +
 +
Combining,
 +
 +
<math>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)</math>.
 +
 +
Therefore, we have found the recurrence relation <math>f(m,n)=4f(m,n-1)-f(m+1,n-1)</math>.
 +
 +
We can see that <math>f(m,0)=\frac{(2m)!}{m!m!}</math> is integral because the RHS is just <math>_{2m} C _m</math>, which we know to be integral for all <math>m \geq 0</math>.
 +
 +
So, <math>f(m,1)=4f(m,0)-f(m+1,0)</math> must be integral, and then <math>f(m,2)=4f(m,1)-f(m+1,1)</math> must be integral, etc.
 +
 +
By induction, <math>f(m,n)</math> is integral for all <math>m,n \geq 0</math>.

Revision as of 09:13, 20 October 2014

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1972_IMO_Problems/Problem_3&oldid=65340"