IMO 1994 SL A5

Origin: POL | Category: Algebra

Problem

Let f(x) = x2+1 2x for x ̸= 0. Define f (0)(x) = x and f (n)(x) = f(f (n−1)(x)) for all positive integers n and x ̸= 0. Prove that for all nonnegative integers n and x ̸= −1, 0, or 1, f (n)(x) f (n+1)(x) = 1 + f  x+1 x−1 2n.

Solution

If f (n)(x) = pn(x) qn(x) for some positive integer n and polynomials pn, qn, then f (n+1)(x) = f pn(x) qn(x)  = pn(x)2 + qn(x)2 2pn(x)qn(x) .

Note that f (0)(x) = x/1. Thus f (n)(x) = pn(x) qn(x), where the sequence of polynomials pn, qn is defined recursively by p0(x) = x, q0(x) = 1, and pn+1(x) = pn(x)2 + qn(x)2, qn+1(x) = 2pn(x)qn(x). Furthermore, p0(x) \pm q0(x) = x \pm 1 and pn+1(x) \pm qn+1(x) = pn(x)2 + qn(x)2 \pm 2pn(x)qn(x) = (pn(x) \pm qn(x))2, so pn(x) \pm qn(x) = (x \pm 1)2n for all n. Hence pn(x) = (x + 1)2n + (x −1)2n and qn(x) = (x + 1)2n −(x −1)2n . Finally, f (n)(x) f (n+1)(x) = pn(x)qn+1(x) qn(x)pn+1(x) = 2pn(x)2 pn+1(x) = ((x + 1)2n + (x −1)2n)2 (x + 1)2n+1 + (x −1)2n+1 = 1 +  x+1 x−1 2n 1 +  x+1 x−1 2n+1 = 1 + f  x+1 x−1 2n.