22nd Putnam 1961

The sequence of non-negative reals satisfies a_n+m ≤ a_na_m for all m, n. Show that lim a_n^1/n exists.

Solution

a_n ≤ a₁a_n-1 ≤ a₁²a_n-2 ≤ ... ≤ a₁ⁿ. So a_n^1/n ≤ a₁. All a_n are non-negative, so a_n^1/n ≥ 0. Thus we have established that {a_n^1/n} is bounded.

Fix n. Take any N > n. Then we may write N = nq + r, with 0 ≤ r < n. We have a_N ≤ a_n^q a_r , so a_N^1/N ≤ a_n^s a_r^1/N, where s = q/N = (1 - r/N)/n. But (1 - r/N) tends to 1 as N tends to infinity, as does a_r^1/N. Hence lim sup a_N^1/N ≤ a_n^1/n. This is true for all n, so the sequence cannot have more than one limit point and hence converges.

22nd Putnam 1961

© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002