Difference between revisions of "1972 IMO Problems/Problem 3"
(→Solution) |
(→Solution) |
||
Line 9: | Line 9: | ||
First, let's look at <math>f(m,n-1)</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 | + | <math>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) \frac{(n-1)(m+n)}{(2n-1)(2n-2)}=f(m,n) \frac{m+n}{2(2n-1)}</math> |
Second, let's look at <math>f(m+1,n-1)</math>: | Second, let's look at <math>f(m+1,n-1)</math>: |
Revision as of 19:54, 20 November 2018
Let and be arbitrary non-negative integers. Prove that is an integer. (.)
Solution
Let . We intend to show that is integral for all . To start, we would like to find a recurrence relation for .
First, let's look at :
Second, let's look at :
Combining,
.
Therefore, we have found the recurrence relation .
We can see that is integral because the RHS is just , which we know to be integral for all .
So, must be integral, and then must be integral, etc.
By induction, is integral for all .
Borrowed from http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html