a Use induction to show that using only 3c stamps and 5c sta

(a) Use induction to show that using only 3c/ stamps and 5c/ stamps, any postage amount 8c/ or greater can be formed. (This can be done neatly using either form of induction.)

(b) Redo the previous problem using which ever form of induction you didn

Solution

Perhaps they are referring to either strong or weak induction. Strong induction is if you go through several base cases and apply these in the inductive step. Let me see about the weak version:

Base case 1: 8 = 5+3

So assume that we can form any integer between 8 and n, including both, using only 5\'s and 3\'s. Then us see if we can form n+1 as a combination of 5 and 3:

Since n+1>8 we can write it as n+1=8q+d where q and d are positive integers with q>1 and d<8. Then

n+1 = 8q+d
= 5q+3q+d

If d=0, d=3 or d=5 we either have

n+1=5q+3q
or
n+1=5q+3(q+1)
or
n+1=5(q+1)+3q

Otherwise d can be 1,2,4,6 or 7. If d>3 we can write

n+1=5(q-1)+3q+(5+d)

where 8<5+d<n+1 so that 5+d can be written as a sum of 5\'s and 3\'s. If d=1 we have 5+d=6 which can be written as 2