### IMO 1985

Problem B3

For every real number x1, construct the sequence x1, x2, ... by setting:

xn+1 = xn(xn + 1/n).

Prove that there exists exactly one value of x1 which gives 0 < xn < xn+1 < 1 for all n.

Solution

Define S0(x) = x, Sn(x) = Sn-1(x) (Sn-1(x) + 1/n). The motivation for this is that xn = Sn-1(x1).

Sn(0) = 0 and Sn(1) > 1 for all n > 1. Also Sn(x) has non-negative coefficients, so it is strictly increasing in the range [0,1]. Hence we can find (unique) solutions an, bn to Sn(an) = 1 - 1/n, Sn(bn) = 1.

Sn+1(an) = Sn(an) (Sn(an) + 1/n) = 1 - 1/n > 1 - 1/(n+1), so an < an+1. Similarly, Sn+1(bn) = Sn(bn) (Sn(bn) + 1/n) = 1 + 1/n > 1, so bn > bn+1. Thus an is an increasing sequence and bn is a decreasing sequence with all an less than all bn. So we can certainly find at least one point x1 which is greater than all the an and less than all the bn. Hence 1 - 1/n < Sn(x1) < 1 for all n. But Sn(x1) = xn+1. So xn+1 < 1 for all n. Also xn > 1 - 1/n implies that xn+1 = xn(xn + 1/n) > xn. Finally, we obviously have xn > 0. So the resulting series xn satisfies all the required conditions.

It remains to consider uniqueness. Suppose that there is an x1 satisfying the conditions given. Then we must have Sn(x1) lying in the range 1 - 1/n, 1 for all n. [The lower limit follows from xn+1 = xn(xn + 1/n).] Hence we must have an < x1 < bn for all n. We show uniqueness by showing that bn - an tends to zero as n tends to infinity. Since all the coefficients of Sn(x) are non-negative, it is has increasing derivative. Sn(0) = 0 and Sn(bn) = 1, so for any x in the range 0, bn we have Sn(x) ≤ x/bn. In particular, 1 - 1/n < an/bn. Hence bn - an ≤ bn - bn(1 - 1/n) = bn/n < 1/n, which tends to zero.

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.