1.8 Induction

Proofs using the three principles, Ordinary Induction, Strong Induction, and Well Ordering, are equivalent - a proof of a theorem using one of them can be reformatted into a proof using either of the other two without additional insights. In this postage problem, however, Ordinary Induction requires an extra quantifier in the induction hypothesis, making the two other approaches more straightforward.

Specifically, strong induction is a good choice for this problem, using the straightforward induction hypothesis

\(P(n)::= \)[4-cent and 5-cent stamps can form \(n \)-cent postage]

with the base cases \(n = 12, 13, 14, \text{ and } 15.\)

Using the Well Ordering Principle is also straightforward. The proof could start with the set of all counterexamples, namely,

\(\{n \ge 12 \;| \; n \text{-cent postage CANNOT be formed with } 4 \text{-cent and } 5 \text{-cent stamps } \} \)

Assuming that this set is not empty, the Well Ordering Principle implies that it has a minimum element. A contradiction can then be proved using the same base cases as those in the Strong Induction proof and the same reasoning as in the inductive step.

Let's try Ordinary Induction. Below is the induction hypothesis, \(Q(n)\), with the addition \(\forall \):

\(Q(n)::= \forall k, 12 \le k \le n. [4 \text{-cent and } 5 \text{-cent stamps can form } k \text{-cent postage}]\)

Having proved \(\forall n.Q(n)\) by Ordinary Induction, the desired assertion about postage: \(\forall n\ge 12.P(n)\) would then be an immediate corollary.