Let n be an integer greater than 2. Define the sequence am by a1 = n, am+1 = n to the power of am. Either show that am < n!! ... ! (where the factorial is taken m times), or show that am > n!! ... ! (where the factorial is taken m-1 times).
Solution
If it was true that nk < k!. then the upper limit on am would be almost trivial. Unfortunately, nk > k! for small k, which results in a few complications. Let nm = n! ... ! (m times). We will prove that am < nm 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 > 2n2. So, a fortiori, nm > 2n2 for m ≥ 1. It is easy to check that for n = 3, a2 = 27 < n2 = 3!! = 720, so the result is true for m = 2. Also n2 > 2n2 = 18. Similarly, for n = 4, a2 = 256 < n2 = 4!! = 24! which establishes the result for m = 2. Also n2 > 2n2 = 32. So for all n we have a starting case m for which also nm > 2n2.
If k ≥ 2n2, then half the terms in k! are at least n2, so their product is at least n2 k/2 = nk. In other words k! > nk. So suppose that am < nm, (*). Then since nm > 2n2, we may take (*) to the power of n to get am+1 = nlhs < nrhs < nm+1. Hence the result is true for all m.
The lower limit is harder because it is not true that nk > k! , so the result for m+1 does not follow in an immediate way from that for m.
Let f0(n) = n, f1(n) = f0(n) n!, f2(n) = f1(n) n!! , f3(n) = f2(n) n!!!, ... . We show that fm+1(n) < n to the power of fm(n). We use induction on m. For m = 0, this reads n n! < nn, which is obviously true. Now assume it is true for m and all n. Then we have fm+1(n) = n fm(n!) < n (n! to the power of fm-1(n!) ) < (n n!) to the power of fm-1(n!) < nn to the power of fm-1(n!) = n to the power of fm(n).
It is now an easy induction that fm(n) < am+1. For m = 1, this just states that n n! < nn. Suppose it is true for m, then fm+1(n) < n to the power of fm(n) < n to the power of am+1 = am+2. But obviously n! ... ! (! taken m times) < fm(n) and hence < am+1.
© John Scholes
jscholes@kalva.demon.co.uk
15 Feb 2002