4 Use weak induction to show that any integer amount of post

4. Use weak induction to show that any integer amount of postage from 18 cents on up can be made from an infinite supply of 4-cent and 7-cent stamps. Your solution must clearly identify the basis, the inductive hypothesis and describe the inductive step. Note, your description of the inductive step need not contain lots of mathematical symbols or complex formulas. It should be stated in plain English using the basis and the hypothesis that you provided.

Re-write the basis and the hypothesis that you developed for question 4, above, as correct basis and the appropriate hypothesis for a proof by strong induction. (You don\'t need to complete the step; we\'re interested in what changes you made to the original base case(s) and hypothesis.)

Solution

base case :

18 = 7*2 + 4*1

induction hypothesis A(n) true for n=k

A(n) : n = p*7 + q* 4 where p,q>=0 and either p>=1 or q>=5

for the strong induction basis:

18= 7*2 +4

19 = 7*1 + 4*3

20 = 7*0 + 4*5

21 = 7*3 + 4*0

inductive step : A(k+1)

k = p*7 + q*4

if p>=1

k+1 = (p-1)*7 + (q+2)*4

if q>=5

k+1 = (p+3)*7 +(q-5)*4

So A(k+1) is true

induction hypothesis A(n) true for n<=k

A(n) : n = p*7 + q* 4 where p,q>=0

induction step

A(k+1) true

k + 1 -4 = k-3 = p*7 + q*4 where p,q >=0

K+1 = p*7 + (q+1) *4