1995 USAMO Problems/Problem 4

Problem

Suppose $q_1,q_2,...$ is an infinite sequence of integers satisfying the following two conditions:

(a) $m - n$ divides $q_m - q_n$ for $m>n \geq 0$

(b) There is a polynomial $P$ such that $|q_n|<P(n)$ for all $n$ .

Prove that there is a polynomial $Q$ such that $q_n = Q(n)$ for each $n$ .

Solution

Step 1: Suppose $P$ has degree $d$ . Let $Q$ be the polynomial of degree at most $d$ with $Q(x)=q_x$ for $0\leq x\leq d$ . Since the $q_x$ are all integers, $Q$ has rational coefficients, and there exists $k$ so that $kQ$ has integer coefficients. Then $m-n|kQ(m)-kQ(n)$ for all $m,n\in \mathbb N_0$ .

Step 2: We show that $Q$ is the desired polynomial.

Let $x>n$ be given. Now $kq_x\equiv kq_m\pmod{x-m}\text{ for all integers }m\in[0,d]$ Since $kQ(x)$ satisfies these relations as well, and $kq_m=kQ(m)$ , $kq_x\equiv kQ(x)\pmod{x-m}\text{ for all integers }m\in[0,d]$ and hence $kq_x\equiv kQ(x)\pmod{\text{lcm}(x,x-1,\ldots, x-d)}. \;(1)$ Now $\begin{align*} \text{lcm}(x,x-1,\ldots, x-i-1)&=\text{lcm}[\text{lcm}(x,x-1,\ldots, x-i),x-i-1]\\ &=\frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[\text{lcm}(x,x-1,\ldots, x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{\text{gcd}[x(x-1)\cdots(x-i),(x-i-1)]}\\ &\geq \frac{\text{lcm}(x,x-1,\ldots, x-i)(x-i-1)}{(i+1)!} \end{align*}$ so by induction $\text{lcm}(x,x-1,\ldots, x-d)\geq \frac{x(x-1)\cdots (x-d)}{d!(d-1)!\cdots 1!}$ . Since $P(x), Q(x)$ have degree $d$ , for large enough $x$ (say $x>L$ ) we have $\left|Q(x)\pm\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}\right|>P(x)$ . By (1) $kq_x$ must differ by a multiple of $\text{lcm}(x,x-1,\ldots, x-d)$ from $kQ(x)$ ; hence $q_x$ must differ by a multiple of $\frac{x(x-1)\cdots (x-d)}{kd!(d-1)!\cdots 1!}$ from $Q(x)$ , and for $x>L$ we must have $q_x=Q(x)$ .

Now for any $y$ we have $kQ(y)\equiv kQ(x)\equiv kq_x \equiv kq_y\pmod{x-y}$ for any $x>L$ . Since $x-y$ can be arbitrarily large, we must have $Q(y)=q_y$ , as needed.

1995 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1995 USAMO Problems/Problem 4

Problem

Solution

See Also