IMO 1992 SL 18

Origin: USA

Problem

Let [x] denote the greatest integer less than or equal to x. Pick any x1 in [0, 1) and define the sequence x1, x2, x3, . . . by xn+1 = 0 if xn = 0 and xn+1 = 1/xn −[1/xn] otherwise. Prove that x1 + x2 + \cdot \cdot \cdot + xn < F1 F2

• F2 F3
• \cdot \cdot \cdot + Fn Fn+1 , where F1 = F2 = 1 and Fn+2 = Fn+1 + Fn for n \geq1.

Solution

Let us define inductively f 1(x) = f(x) = x+1 and f n(x) = f(f n−1(x)), and let gn(x) = x + f(x) + f 2(x) + \cdot \cdot \cdot + f n(x). We shall prove first the following statement.

Lemma. The function gn(x) is strictly increasing on [0, 1], and gn−1(1) = F1/F2 + F2/F3 + \cdot \cdot \cdot + Fn/Fn+1. Proof. Since f(x) −f(y) = y−x (1+x)(1+y) is smaller in absolute value than x −y, it follows that x > y implies f 2k(x) > f 2k(y) and f 2k+1(x) < f 2k+1(y), and moreover that for every integer k \geq0, [f 2k(x) −f 2k(y)] + [f 2k+1(x) −f 2k+1(y)] > 0. Hence if x > y, we have gn(x)−gn(y) = (x−y)+ [f(x)−f(y)]+\cdot \cdot \cdot+ [f n(x) −f n(y)] > 0, which yields the first part of the lemma. The second part follows by simple induction, since f k(1) = Fk+1/Fk+2. If some xi = 0 and consequently xj = 0 for all j \geqi, then the problem reduces to the problem with i−1 instead of n. Thus we may assume that all x1, . . . , xn are different from 0. If we write ai = [1/xi], then xi = ai+xi+1 . Thus we can regard xi as functions of xn depending on a1, . . . , an−1. Suppose that xn, an−1, . . . , a3, a2 are fixed. Then x2, x3, . . . , xn are all fixed, and x1 = a1+x2 is maximal when a1 = 1. Hence the sum S = x1 + x2 + \cdot \cdot \cdot + xn is maximized for a1 = 1. We shall show by induction on i that S is maximized for a1 = a2 = \cdot \cdot \cdot = ai = 1. In fact, assuming that the statement holds for i −1 and thus a1 = \cdot \cdot \cdot = ai−1 = 1, having xn, an−1, . . . , ai+1 fixed we have that xn, . . . , xi+1 are also fixed, and that xi−1 = f(xi), . . . , x1 = f i−1(xi). Hence by the lemma, S = gi−1(xi) + xi+1 + \cdot \cdot \cdot + xn is maximal when xi = ai+xi+1 is maximal, that is, for ai = 1. Thus the induction is complete. It follows that x1 + \cdot \cdot \cdot + xn is maximal when a1 = \cdot \cdot \cdot = an−1 = 1, so that x1 + \cdot \cdot \cdot + xn = gn−1(x1). By the lemma, the latter does not exceed gn−1(1). This completes the proof. Remark. The upper bound is the best possible, because it is approached by taking xn close to 1 and inductively (in reverse) defining xi−1 = 1+xi = ai+xi .