### 22nd Putnam 1961

**Problem B5**

Let n be an integer greater than 2. Define the sequence a_{m} by a_{1} = n, a_{m+1} = n to the power of a_{m}. *Either* show that a_{m} < n!! ... ! (where the factorial is taken m times), *or* show that a_{m} > n!! ... ! (where the factorial is taken m-1 times).

**Solution**

If it was true that n^{k} < k!. then the upper limit on a_{m} would be almost trivial. Unfortunately, n^{k} > k! for small k, which results in a few complications. Let n_{m} = n! ... ! (m times). We will prove that a_{m} < n_{m} by induction on m. For m = 1, the result just states that n < n!, which is obviously true. Suppose now that n ≥ 5. Then n! ≥ n(n-1)3 > 2n^{2}. So, a fortiori, n_{m} > 2n^{2} for m ≥ 1. It is easy to check that for n = 3, a_{2} = 27 < n_{2} = 3!! = 720, so the result is true for m = 2. Also n_{2} > 2n^{2} = 18. Similarly, for n = 4, a_{2} = 256 < n_{2} = 4!! = 24! which establishes the result for m = 2. Also n_{2} > 2n^{2} = 32. So for all n we have a starting case m for which also n_{m} > 2n^{2}.

If k ≥ 2n^{2}, then half the terms in k! are at least n^{2}, so their product is at least n^{2 k/2} = n^{k}. In other words k! > n^{k}. So suppose that a_{m} < n_{m}, (*). Then since n_{m} > 2n^{2}, we may take (*) to the power of n to get a_{m+1} = n^{lhs} < n^{rhs} < n_{m+1}. Hence the result is true for all m.

The lower limit is harder because it is not true that n^{k} > k! , so the result for m+1 does not follow in an immediate way from that for m.

Let f_{0}(n) = n, f_{1}(n) = f_{0}(n) n!, f_{2}(n) = f_{1}(n) n!! , f_{3}(n) = f_{2}(n) n!!!, ... . We show that f_{m+1}(n) < n to the power of f_{m}(n). We use induction on m. For m = 0, this reads n n! < n^{n}, which is obviously true. Now assume it is true for m ** and all n**. Then we have f_{m+1}(n) = n f_{m}(n!) < n (n! to the power of f_{m-1}(n!) ) < (n n!) to the power of f_{m-1}(n!) < n^{n} to the power of f_{m-1}(n!) = n to the power of f_{m}(n).

It is now an easy induction that f_{m}(n) < a_{m+1}. For m = 1, this just states that n n! < n^{n}. Suppose it is true for m, then f_{m+1}(n) < n to the power of f_{m}(n) < n to the power of a_{m+1} = a_{m+2}. But obviously n! ... ! (! taken m times) < f_{m}(n) and hence < a_{m+1}.

22nd Putnam 1961

© John Scholes

jscholes@kalva.demon.co.uk

15 Feb 2002