43rd Putnam 1982

Problem B5

Given x > ee, define the sequence f(n) as follows: f(0) = e, f(n+1) = (ln x)/(ln f(n)). Prove that the sequence converges. Let the limit be g(x). Prove that g is continuous.

Solution

We establish that f(2n) is an increasing sequence, and f(2n-1) a decreasing sequence. Specifically we show that e < f(2n) < f(2n+2) < f(2n+1) < f(2n-1) (*). We need the preliminary result that if e < x < y, then xy > yx (**). We also use repeatedly the obvious result that if 1 < x < y and xa = yb, then a > b (***).

To prove (**), let k(x) = (ln x)/x, then k'(x) = (1 - ln x)/x2 < 0 for x > e. Hence for e ≤ x < y, (ln x)/x > (ln y)/y, and hence y ln x > x ln y, and hence xy > yx.

We establish (*) by induction. By definition, we have x = f(n)f(n+1). In particular, x = ef(1). We are given that x > ee, so certainly f(1) > e. Applying (**), ef(1) > f(1)e. But x = ef(1) = f(1)f(2), so f(2) > e. Also since e < f(1) and ef(1) = f(1)f(2) we have f(1) > f(2). So we have established that e < f(2) < f(1).

Now assume that e < f(2n) < f(2n-1). By definition, x = f(2n-1)f(2n) = f(2n)f(2n+1). But f(2n-1) > f(2n), so by (***) f(2n) < f(2n+1). Also, using (**), f(2n) < f(2n-1) implies x = f(2n-1)f(2n) < f(2n)f(2n-1). Hence f(2n+1) < f(2n-1). So we have established that f(2n) < f(2n+1) < f(2n-1).

We now use f(2n)f(2n+1) = f(2n+1)f(2n+2). Since f(2n) < f(2n+1), (***) gives f(2n+1) > f(2n+2). Also, using (**), f(2n)f(2n+1) > f(2n+1)f(2n), so f(2n+2) > f(2n). So we have established that f(2n) < f(2n+2) < f(2n+1) < f(2n-1). That completes the induction.

Hence f(2n) is an increasing sequence which is bounded above. So it must converge to some limit h. Similarly, f(2n+1) is a decreasing sequence which is bounded below. So it must converge to some limit k. Also we have h, k > e. But it follows that lim f(2n)f(2n+1) = hk and lim f(2n+1)f(2n+2) = kh. But both these sequences have the constant value x. Hence hk = kh. If h and k were unequal, then (**) would imply that hk and kh were unequal. Hence h = k.

So we have established that the sequence f(n) converges to some limit g(x). We have also shown that g(x)g(x) = x. But yy is continuous and strictly increasing, so its inverse g(x) is continuous.