Use weak induction to show that any integer amount of postag

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.

Solution

To start with x=1, y =2 is a solution of 4x+2y=18, so there is a (positive solution ) for 18 cents.

Now any integral solution of 4a +7b =1 is of the form

a = -7m+2, b =4m-1, m any integer.................................................(1)

Assume the induction hypothesis for k >=18.

That is there exist positive solutions x and y such that

4x+7y=k........................................................................................(2)

To show that there exist u and v , both positive such that

4u+7v = k+1...................................................................................(3)

This will be the case if there exist positive u and v such that (subtracting (2) from (3))

4(u-x)+7(v-y) =1

From (1) , u-x= -7m+2

                 v-y= 4m-1.

So suffices to find a positive integer m such that x-7m+2 is positive, which is always possible.

Hence , induction is complete. So positive integral solutions always exist for

                                 4x+7y= q for any integer >=18