1995 USAMO Problems/Problem 4
Problem
Suppose is an infinite sequence of integers satisfying the following two conditions:
(a) divides for
(b) There is a polynomial such that for all .
Prove that there is a polynomial such that for each .
Solution
Step 1: Suppose has degree . Let be the polynomial of degree at most with for . Since the are all integers, has rational coefficients, and there exists so that has integer coefficients. Then for all .
Step 2: We show that is the desired polynomial.
Let be given. Now Since satisfies these relations as well, and , and hence Now so by induction . Since have degree , for large enough (say ) we have . By (1) must differ by a multiple of from ; hence must differ by a multiple of from , and for we must have .
Now for any we have for any . Since can be arbitrarily large, we must have , as needed.
See Also
1995 USAMO (Problems • Resources) | ||
Preceded by Problem 3 |
Followed by Problem 5 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.