1.2 Mathematical Induction 5The third example is a problem from the 5th W.L. Putnam Mathematical Competition,
and it was selected because its solution combines several proofs by induction. If you find
it too demanding, think of Vincent van Gogh’s words: “The way to succeed is to keep
your courage and patience, and to work energetically.’’
Example.Forma positive integer andnan integer greater than 2, definef 1 (n)=n,
f 2 (n)=nf^1 (n),...,fi+ 1 (n)=nfi(n),....Prove that
fm(n)<n!!···!<fm+ 1 (n),where the term in the middle hasmfactorials.
Solution.For convenience, let us introduceg 0 (n) = n, and recursivelygi+ 1 (n) =
(gi(n))!. The double inequality now reads
fm(n)<gm(n)<fm+ 1 (n).Form=1 this is obviously true, and it is only natural to think of this as the base case. We
start by proving the inequality on the left by induction onm. First, note that ift> 2 n^2
is a positive integer, then
t!>(n^2 )t−n
2
=ntnt−^2 n
2
>nt.Now, it is not hard to check thatgm(n) > 2 n^2 form≥2 andn≥3. With this in mind,
let us assume the inequality to be true form=k. Then
gk+ 1 (n)=(gk(n))!>ngk(n)>nfk(n)=fk+ 1 (n),which proves the inequality form=k+1. This verifies the inductive step and solves
half of the problem.
Here we pause for a short observation. Sometimes the proof of a mathematical
statement becomes simpler if the statement is strengthened. This is the case with the
second inequality, which we replace by the much stronger
g 0 (n)g 1 (n)···gm(n)<fm+ 1 (n),holding true formandnas above.
As an intermediate step, we establish, by induction onm, that
g 0 (n)g 1 (n)···gm(n)<ng^0 (n)g^1 (n)···gm−^1 (n),for allmand alln≥3. The base casem=1 is the obviousn·n!<nn. Now assume
that the inequality is true form=k, and prove it form=k+1. We have