Difference between revisions of "1972 IMO Problems/Problem 3"
(→Solution 1) |
(→Solution 1) |
||
Line 28: | Line 28: | ||
Note that <math>f(m,0)</math> is just <math>\binom{2m}{m}</math>, which is an integer for all <math>m \geq 0</math>. Then <cmath>f(m,1)=4f(m,0)-f(m+1,0),</cmath> so <math>f(m,1)</math> is an integer, and therefore <math>f(m,2)=4f(m,1)-f(m+1,1)</math> must be an integer, etc. | Note that <math>f(m,0)</math> is just <math>\binom{2m}{m}</math>, which is an integer for all <math>m \geq 0</math>. Then <cmath>f(m,1)=4f(m,0)-f(m+1,0),</cmath> so <math>f(m,1)</math> is an integer, and therefore <math>f(m,2)=4f(m,1)-f(m+1,1)</math> must be an integer, etc. | ||
+ | |||
By induction, <math>f(m,n)</math> is an integer for all <math>m,n \geq 0</math>. | By induction, <math>f(m,n)</math> is an integer for all <math>m,n \geq 0</math>. | ||
Revision as of 13:41, 22 August 2022
Let and
be arbitrary non-negative integers. Prove that
is an integer. (
.)
Solution 1
Denote the given expression as . 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
Note that is just
, which is an integer for all
. Then
so
is an integer, and therefore
must be an integer, etc.
By induction, is an integer for all
.
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 be the largest positive integer
such that
WTS: For all primes ,
We know
Lemma 2.1: Let be real numbers. Then
Proof of Lemma 2.1: Let and
On the other hand,
It is trivial that (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.
See Also
1972 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |