Week 2

The postage problem we did in class on Sept 19th used complete induction to prove. Here the same problem is proved by simple induction.

P(n): postage of n cents can be formed with 4- and 5-cent stamps.
Claim: \forall n \in N, n >= 12 => P(n).
Proof:
Base Case: for n = 12, 12-cent postage can be made by using three 4-cent stamps. So P(12) is true.
Induction Step: assume n \in N and n >= 12. Also assume P(n) is true, that is postage of n cents can be made by using 4- and 5-cent stamps. Then either n has at least one 4-cent stamp or n doesn't have any 4-cent postage.
Case 1: n has at least one 4-cent stamp. Then for (n + 1) postage, we can exchange that 4-cent stamp to a 5-cent stamp to get one cent more postage. So P(n + 1) is true in this case.
Case 2: n has no 4-cent stamp. Then n must have at least three 5-cent stamps, since 15 is the next natural number after 12 which is a multiple of 5. To get one more postage, we can simply exchange three 5-cent stamps (15 cents) to four 4-cent stamps (16 cents). So P(n + 1) is also true in this case.
Thus, P(n + 1) is true.
So \forall n \in N, (n >= 12 and P(n) ) => P(n + 1)
Therefore, \forall n \in N, n >= 12 => P(n).