### 27th Putnam 1966

Problem A3

Define the sequence {an} by a1 ∈ (0, 1), and an+1 = an(1 - an). Show that limn→∞n an = 1.

Solution

We show first that an < 1/(n+1) for all n > 1. We have a1(1 - a1) = 1/4 - (a1 - 1/2)2 < 1/3, so it is true for n = 2. Also, the quadratic expression shows that an(1 - an) is an increasing function of an for an < 1/2. Hence if an < 1/(n+1), then an+1 < (1 - 1/(n+1) )/(n+1) = n/(n2 + 2n + 1) < n/(n2 + 2n) = 1/(n + 2). Hence, by induction it is true for all n.

Suppose that 1/2 > an > 1/(k + √k). Then an+1 > ( 1/(k + √k) )(1 - 1/(k + √k) ). We show that this is greater than 1/(k+1 + √(k+1) ) for k sufficiently large. We require k2 - 1 + (k + 1)√k + (k - 1)√(k + 1) + √(k2 + k) > k2 + k√k + k. Obviously √(k2 + k) > k, so it is sufficient to show that (k - 1)√(k + 1) > (k - 1)√k + 1. But this is almost obvious since √(k + 1) > √k + 1/(3√k), and (k - 1) > 3√k for k > 11.

Now a1 > 0, so a1 > 1/(k + √k) for some k. Increasing k if necessary, we can take k > 11. It then follows by induction that an > 1(n + k + √(n + k)) for all n, where k is fixed. Hence n an lies between n/(n + k + √(n + k)) and n/(n + 1). But both n/(n + k + √(n + k)) and n/(n + 1) converge to 1, so n an does also.