Let p(x) be a cubic polynomial with rational coefficients. q1, q2, q3, ... is a sequence of rationals such that qn=p(qn+1) for all positive n. Show that for some k, we have qn+k=qn for all positive n.
Problem
Source: IMO ShortList 1990, Problem 26 (USA 2)
Tags: algebra, polynomial, number theory, Cubic, Iteration, IMO Shortlist
10.04.2005 11:02
Suppose that p(x)=1/e(ax3+bx2+cx+d) where a,b,c,d,e∈Z, e>0. Then suppose that m,M∈Z, n,N∈N, the fractions mn , MN are reduced and p(mn)=MN. But p(mn)=am3+bm2n+cmn2+dn3en3. Suppose k=gcd(am3+bm2n+cmn2+dn3,en3). Denote also x=am3, y=bm2n+cmn2+dn3. Then k|x+y and k|en3. Therefore k|e(x3+y3) ( because x+y|x3+y3) , but k|en3|ey3, so k|ex3=ea3m9 , and as before k|en3. So, at the end, k|ea3m9,ea3n3. But gcd(m9,n3)=1, therefore k|ea3. So we get that gcd(am3+bm2n+cmn2+dn3,en3)|ea3, therefore Mea3⩾ , so n \leqslant a \sqrt[3]{M} . Now suppose we have a sequence of rational numbers q_{1},q_{2}, \ldots such that q_{n} = p(q_{n+1}) . Write q_{n} = \frac{a_{n}}{b_{n}} as a reduced fraction where a_{n},b_{n} \in \mathbb{Z} , b_{n} > 0 . Then, as we saw before, b_{n+1} \leqslant a \sqrt[3]{b_{n}} . Therefore the sequence \{ b_{n} \} is bounded. Also note that the sequence \{ q_{n} \} is bounded. Indeed, there exists some C > 0 such that for every x \in \mathbb{R} , |x| > C we have |p(x)| > 2|x| . Therefore it is impossible that |q_{n}| > C for infinitely many n 's, because q_{1} is bounded. So \{ b_{n} \} is bounded and \{ q_{n} \} is bounded, therefore \{ a_{n} \} is bounded. Therefore the sequence q_{n} takes only a finite number of values. Therefore there exists a rational number q , which appears in the sequence \{ q_{n} \} infinitely many times. Because the number q appears at least two times, there is k \in \mathbb{N} , such that \underbrace{p \circ p \circ \ldots \circ p}_{k times} (q) = q . Therefore k is a period for q_{n} , because there exists N as large as we want, such that q_{N} = q , so because of q_{n-1} = p(q_{n}) , we get that q_{n-k} = q_{n} for every k+1 \leqslant n \leqslant N . So because we can take N to be as large as we want, we get that q_{n-k} = q_{n} for every k+1 \leqslant n . Therefore q_{n} is periodic.