70 CHAPTER 1 Sets, Proof Templates, and Induction
Constructing a proof by induction using the Strong Form of Induction requires a dif-
ferent template than the one for the first Principle of Mathematical Induction. This new
template makes clear what is being done at each step, but be careful: There is more variety
in the form of proofs using the Strong Form of Induction than in proofs using the ordinary
Principle of Mathematical Induction.Temlat 1.3 Uin h Strn For of MahmaiaTo construct a proof using the Strong Form of Mathematical Induction, choose an
no E N appropriate to the problem. Let
T = {n E N : n > no and property P holds of n}
(Base step) Show explicitly that property P holds for certain numbers n, called the
base cases. no should be one of those values; the choice of the other values depend on
the problem.
(Inductive step) For all n > no not covered in the base case, assume that property
P holds for all k = no, no + 1 .... n - 1, and prove that property P holds for n.
Infer by the Strong Form of Mathematical Induction that
T = {n E N : n > no)Using the Strong Form of Mathematical Induction
As in an ordinary inductive proof, an inductive proof using the strong form of induction
has three essential parts: (i) a base step, (ii) an inductive step, and (iii) an application of the
Strong Form of Mathematical Induction.
Translating the problem includes specifying no and clearly defining the set T whose
elements the inductive proof will determine-that is, clearly stating the property P to beverified. This definition does not tell us that any number is in T.
The first step of the proof is called the base step, and it involves proving the result for
the base case(s). Identify one or more values for which property P can be verified directly.
Often, one might verify it directly for values no, no + 1, no + 2, ... ., n for some n 1 > no.
In the base step of the proof, prove directly that no, no + 1 .... n 1 E T. As in Example 1,
the base cases often correspond to the initial conditions specified in the problem.
The inductive step is usually quite different in the Strong Form of Mathematical Induc-
tion from the inductive step in the Principle of Mathematical Induction. Begin by letting
n > no be an arbitrary natural number that is not covered in the base case. Assume thatno, no + 1 .... n - 1 E T. To complete the inductive step, use that assumption to show
that n E T. Again, start by writing out property P for n to see what is to be proved. There
is no real formula for the next part of the inductive proof. Figure out how to prove property
P holds for n knowing that property P holds for no, no + 1 .... n - 1. When that is done,
use the Strong Form of Mathematical Induction to infer that for all n > no, n E T.