# Thread: Postage stamp problem: Weak versus Strong Induction

1. ## Postage stamp problem: Weak versus Strong Induction

I am instructed to prove that postage amounts greater than or equal to 54 can be taken care of using solely 7 and 10 cent stamps. The book asks me to use strong induction.

My Basis is:

54 = 4*10 + 2*7

My inductive step is:

(assume n = 10*j + 7*k for some n >= 54 and j,k are integers)

n + 1 = 10(j - 2) + 7(k + 3)

So the inductive step infers (as far as I can see) that if the hypothesis is true for n, it is true for n + 1. The basis is shown to be true.

It seems to me that this concludes a proof by WEAK induction, but the solutions manual presents a nearly identical argument and calls it strong induction.

2. ## Re: Postage stamp problem: Weak versus Strong Induction

Originally Posted by jmedsy
My inductive step is:

(assume n = 10*j + 7*k for some n >= 54 and j,k are integers)

n + 1 = 10(j - 2) + 7(k + 3)
It is important that the induction hypothesis says n = 10*j + 7*k for some n >= 54 and nonnegative integers j, k. Then j - 2 is not necessarily a nonnegative integer, so you have not proved that n is represented in a required way.

There are two options. One is to consider the cases j = 0 and j = 1 separately. This would still be a proof by regular induction. Another is to prove P(n) -> P(n + 7) where P is the induction hypothesis above. The induction step is obvious, but you need strong induction (though, strictly speaking, you use only P(n) and not P(k) for all 54 <= k < n + 7 in the proof of P(n + 7)). You also need to prove 7 bases cases.