Paragraph

As a final contrast between the two forms of induction, consider once more the stamp problem. Regular induction worked by showing how to increase postage by one cent (either replacing three 5-cent stamps with two 8-cent stamps, or three 8-cent stamps with five 5-cent stamps). We could give a slightly different proof using strong induction. First, we could show five base cases: it is possible to make 28, 29, 30, 31, and 32 cents (we would actually say how each of these is made). Now assume that it is possible to make \(k\) cents of postage for all \(k \lt n\) as long as \(k \ge 28\text{.}\) As long as \(n > 32\text{,}\) this means in particular we can make \(k = n-5\) cents. Now add a 5-cent stamp to get make \(n\) cents.