Putnam 1966/A3 solution

27th Putnam 1966

Problem A3

Define the sequence {a_n} by a₁ ∈ (0, 1), and a_n+1 = a_n(1 - a_n). Show that lim_n→∞n a_n = 1.

Solution

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

Suppose that 1/2 > a_n > 1/(k + √k). Then a_n+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 k² - 1 + (k + 1)√k + (k - 1)√(k + 1) + √(k² + k) > k² + k√k + k. Obviously √(k² + 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 a₁ > 0, so a₁ > 1/(k + √k) for some k. Increasing k if necessary, we can take k > 11. It then follows by induction that a_n > 1(n + k + √(n + k)) for all n, where k is fixed. Hence n a_n 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 a_n does also.

27th Putnam 1966