### 35th IMO 1994 shortlist

Problem A5

Let f(x) = (x2 + 1)/(2x) for x non-zero. Define f0(x) = x and fn+1(x) = f( fn(x) ). Show that for x not -1, 0 or 1 we have fn(x)/fn+1(x) = 1 + 1/f(y), where y = (x+1)N/(x-1)N and N = 2n.

Solution

Define p0(x) = x, q0(x) = 1, pn(x) = pn-1(x)2 + qn-1(x)2, qn(x) = 2pn-1(x) qn-1(x). We show by induction on n that fn(x) = pn(x)/qn(x). It is obviously true for n = 0. So suppose it is true for n.

Then fn+1(x) = (fn(x)2 + 1)/2fn(x) = (pn(x)2 + qn(x)2)/(2 pn(x) qn(x) ) = pn+1(x)/qn+1(x), so the result is also true for n+1 and hence for all n.

Next we show that pn(x) ± qn(x) = (x ± 1)N, where N = 2n. Again we use induction on n. For n = 0 it is immediate. Suppose it is true for n. Then pn+1(x) ± qn+1(x) = pn(x)2 + qn(x)2 ± 2 pn(x) qn(x) = (pn(x) ± qn(x) )2N, so it is true for n+1.

Finally, 1 + 1/f(y) (with y defined as in the question) = 1 + 2y/(y2 + 1) = (y + 1)2/(y2 + 1) = ( (x+1)N + (x-1)N)2/( (x+1)2N + (x-1)2N) = (pn(x) + qn(x) + pn(x) - qn(x) )2/(pn+1(x) + qn+1(x) + pn+1(x) - qn+1(x) ) = 2pn(x)2/pn+1(x). But fn(x)/fn+1(x) = pn(x) qn+1(x)/( pn+1(x) qn(x) ). Substituting for qn+1(x) gives fn(x)/fn+1(x) = 2pn(x)2/pn+1(x) = 1 + 1/f(y).