Maths Olympiad Prep

Library / /14 of 16

Algebra Difficulty 7.4 National Olympiad, round 2 Prove it Romania

A function f:(0,)(0,)f : (0, \infty) \to (0, \infty) is called contractive if, for every numbers x,y(0,)x, y \in (0, \infty), we have limn(fn(x)fn(y))=0\lim_{n \to \infty} (f^n(x) - f^n(y)) = 0, where fn=ffff^n = f \circ f \circ \dots \circ f. Prove

a) If f:(0,)(0,)f : (0, \infty) \to (0, \infty) is contractive, continuous and has a fixed point (there is x0(0,)x_0 \in (0, \infty) such that f(x0)=x0f(x_0) = x_0), then f(x)>xf(x) > x, for x(0,x0)x \in (0, x_0), and f(x)<xf(x) < x, for all x(x0,)x \in (x_0, \infty).

b) The function f:(0,)(0,)f : (0, \infty) \to (0, \infty) defined by f(x)=x+1/xf(x) = x + 1/x is contractive but has no fixed points.

Solution

a) Suppose the contrary, that is ff has another fixed point x1(0,){x0}x_1 \in (0, \infty) \setminus \{x_0\}. Then limn(fn(x0)fn(x1))=x0x10\lim_{n \to \infty} (f^n(x_0) - f^n(x_1)) = x_0 - x_1 \ne 0, a contradiction. In this case, the continuity of ff (intermediate value property) implies f(x)<xf(x) < x, for all x(0,x0)x \in (0, x_0) or f(x)>xf(x) > x, for all x(0,x0)x \in (0, x_0).

By induction, the first case implies 0<fn+1(x)<fn(x)<x0 < f^{n+1}(x) < f^n(x) < x, for any nNn \in \mathbb{N}^* and x(0,x0)x \in (0, x_0). It follows that the sequence an=(fn(x))n1a_n = (f^n(x))_{n \ge 1} is convergent; denote by aa its limit. If a>0a > 0, then from an+1=f(an)a_{n+1} = f(a_n) we get a=f(a)a = f(a), a contradiction. So a=0a = 0, which implies limn(fn(x0)fn(x))=x00\lim_{n \to \infty} (f^n(x_0) - f^n(x)) = x_0 \ne 0, for all x(0,x0)x \in (0, x_0), contradiction. In conclusion f(x)>xf(x) > x, for any x(0,x0)x \in (0, x_0).

Analogously, f(x)>xf(x) > x, for all x(x0,)x \in (x_0, \infty) or f(x)<xf(x) < x for all x(x0,)x \in (x_0, \infty). In the first case we deduce fn+1(x)>fn(x)>xf^{n+1}(x) > f^n(x) > x, for any nNn \in \mathbb{N}^*, implying

limnfn(x)= \lim_{n \to \infty} f^n(x) = \infty
and then limn(fn(x)fn(x0))=\lim_{n \to \infty} (f^n(x) - f^n(x_0)) = \infty, for all x(x0,)x \in (x_0, \infty), a contradiction. So, f(x)<xf(x) < x, for any x(x0,)x \in (x_0, \infty).

b) First solution. Consider x,y(0,)x, y \in (0, \infty). We may suppose f(x)<f(y)f(x) < f(y). Denote xn=fn(x)x_n = f^n(x), nNn \in \mathbb{N}^* and yn=fn(y)y_n = f^n(y), nNn \in \mathbb{N}^*. We have 2xn<yn2 \le x_n < y_n, n>1n > 1, because ff is increasing on [1,)[1, \infty). We shall prove inductively that yn<y1+2ny_n < y_1 + 2\sqrt{n}, nNn \in \mathbb{N}^*. This is obvious for n=1n=1. Supposing yn<y1+2ny_n < y_1 + 2\sqrt{n}, for some nn, by the monotonicity of ff, we get: yn+1=f(yn)<f(y1+2n)=y1+2n+1y1+2n<y1+2n+12n<y1+2n+1y_{n+1} = f(y_n) < f(y_1 + 2\sqrt{n}) = y_1 + 2\sqrt{n} + \frac{1}{y_1 + 2\sqrt{n}} < y_1 + 2\sqrt{n} + \frac{1}{2\sqrt{n}} < y_1 + 2\sqrt{n+1}.

It follows 2xn<yn<y1+2n<3n2 \le x_n < y_n < y_1 + 2\sqrt{n} < 3\sqrt{n}, for nNn \in \mathbb{N}, n>y12n > y_1^2. Using the well-known inequality 1x<ex1 - x < e^{-x}, for xRx \in \mathbb{R}, we deduce: 0<yn+1xn+1=f(yn)f(xn)=(ynxn)(11xnyn)<(ynxn)(119n)<(ynxn)e19n0 < y_{n+1} - x_{n+1} = f(y_n) - f(x_n) = (y_n - x_n) \left(1 - \frac{1}{x_n y_n}\right) < (y_n - x_n) \left(1 - \frac{1}{9n}\right) < (y_n - x_n) e^{-\frac{1}{9n}}, for np=[y12]+1n \ge p = [y_1^2] + 1. We get 0<ynxn<(ypxp)e19k=pn11k0 < y_n - x_n < (y_p - x_p)e^{-\frac{1}{9} \sum_{k=p}^{n-1} \frac{1}{k}}, for all n>pn > p.

Because limnk=pn11k=\lim_{n \to \infty} \sum_{k=p}^{n-1} \frac{1}{k} = \infty, we infer limne19k=pn11k=0\lim_{n \to \infty} e^{-\frac{1}{9} \sum_{k=p}^{n-1} \frac{1}{k}} = 0, which in turn gives limn(fn(y)fn(x))=0\lim_{n \to \infty} (f^n(y) - f^n(x)) = 0. So ff is contractive without fixed points.

Second solution. Using the same notations as before, we shall show that limn(xn2n)=limn(yn2n)=0\lim_{n \to \infty} (x_n - \sqrt{2n}) = \lim_{n \to \infty} (y_n - \sqrt{2n}) = 0, which will imply limn(xnyn)=0\lim_{n \to \infty} (x_n - y_n) = 0, that is the conclusion. As xn+1=xn+1/xnx_{n+1} = x_n + 1/x_n, n1n \ge 1, we have limnxn=\lim_{n \to \infty} x_n = \infty. By the Stolz–Cesàro lemma, we deduce

limn(xn2n)=limnxn22nxn+2n=limnxn+12xn22xn+1xn+2n+22n==limn1/xn21/xn+2/(2n+2+2n)==limn1/xn1+2xn/(2n+2+2n)=0. \begin{align*} \lim_{n \to \infty} (x_n - \sqrt{2n}) &= \lim_{n \to \infty} \frac{x_n^2 - 2n}{x_n + \sqrt{2n}} = \lim_{n \to \infty} \frac{x_{n+1}^2 - x_n^2 - 2}{x_{n+1} - x_n + \sqrt{2n+2} - \sqrt{2n}} = \\ &= \lim_{n \to \infty} \frac{1/x_n^2}{1/x_n + 2/(\sqrt{2n+2} + \sqrt{2n})} = \\ &= \lim_{n \to \infty} \frac{1/x_n}{1 + 2x_n/(\sqrt{2n+2} + \sqrt{2n})} = 0. \end{align*}

The last equality is a consequence of 01/xn1+2xn/(2n+2+2n)1/xn0 \le \frac{1/x_n}{1 + 2x_n/(\sqrt{2n+2} + \sqrt{2n})} \le 1/x_n and limn1/xn=0\lim_{n \to \infty} 1/x_n = 0.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.