1995 USAMO Problems/Problem 4
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 .
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.
|1995 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|