determine which amount of postage can be formed using just 3

determine which amount of postage can be formed using just 3 cent and 10 cent stamps using both mathematical induction and strong induction and how do the two proofs differ.

Solution

3, 6, 9, 10, 12, 13, 15, 16, 18, 19, 20, 21, 22, 23...

Any number ending in 0, 3, 6, 9. Any multiple of 3.Any number greater than 17

-------------------------

a) using the principle of mathematical induction

For the values of 3, 6, 9, 10, 12, 13, 15, and 16,

they are just proven manually so

they won’t be worried about here. But we will show that any postage amount 18 cents or

greater can be formed using 3 and 10 cent stamps using induction.

Base: 18 cents

Formed using six 3 cent stamps.

True.

---

For the inductive hypothesis, we will assume that a

postage amount, n, has been formed

using only 10 and 3 cent stamps. We will then divide this n value up into three cases,

each with an appropriate action to show that postage amount n + 1 is possible

-----

Case 1:

There are no 10 cent stamps.

Action : -Remove three 3 cent stamps and add one 10 cent stamp

Case 2:

There is exactly one 10 cent stamp.

Action: Remove three 3 cent stamps and add one 10 cent stamp.

Case 3:

There are exactly two 10 cent stamps.

Action: Remove the two 10 cent stamps and add seven 3 cent stamps.

This covers all possible cases.

------------------------------------------------------------------------------------------

(b)

using strong induction

For strong induction, three initial cases will need to be shown:

P(19) = one 10 cent stamp and three 3 cent stamps

P(20) = two 10 cent stamps

These will act as bases cases.

For the inductive hypothesis we will assume that some postage value n has been made using only 3

and 10 cent stamps. But since this is strong induction we will also assume that every postage amount from 18 to n cents has successfully formed. Based on this, a solution to P(n + 1) is proposed:

P(n + 1) = P(n – 2) + one 3 cent stam

put in English, any postage amount can be created by taking the solution to the amount three cents less than the amount and adding a 3 cent stamp to it. So P(20) = P(18) + one 3 cent stamp, P(21) = P(19) + one 3 cent stamp, etc.

Since we used strong induction and assumed that everything that came before

P(n) was true, we use the above solution as a strong inductive proof.