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

**Solution**

Define p_{0}(x) = x, q_{0}(x) = 1, p_{n}(x) = p_{n-1}(x)^{2} + q_{n-1}(x)^{2}, q_{n}(x) = 2p_{n-1}(x) q_{n-1}(x). We show by induction on n that f_{n}(x) = p_{n}(x)/q_{n}(x). It is obviously true for n = 0. So suppose it is true for n.

Then f_{n+1}(x) = (f_{n}(x)^{2} + 1)/2f_{n}(x) = (p_{n}(x)^{2} + q_{n}(x)^{2})/(2 p_{n}(x) q_{n}(x) ) = p_{n+1}(x)/q_{n+1}(x), so the result is also true for n+1 and hence for all n.

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

Finally, 1 + 1/f(y) (with y defined as in the question) = 1 + 2y/(y^{2} + 1) = (y + 1)^{2}/(y^{2} + 1) = ( (x+1)^{N } + (x-1)^{N})^{2}/( (x+1)^{2N} + (x-1)^{2N}) = (p_{n}(x) + q_{n}(x) + p_{n}(x) - q_{n}(x) )^{2}/(p_{n+1}(x) + q_{n+1}(x) + p_{n+1}(x) - q_{n+1}(x) ) = 2p_{n}(x)^{2}/p_{n+1}(x). But f_{n}(x)/f_{n+1}(x) = p_{n}(x) q_{n+1}(x)/( p_{n+1}(x) q_{n}(x) ). Substituting for q_{n+1}(x) gives f_{n}(x)/f_{n+1}(x) = 2p_{n}(x)^{2}/p_{n+1}(x) = 1 + 1/f(y).

© John Scholes

jscholes@kalva.demon.co.uk

18 Sep 2002