Clearly state and label as a proposition Pn the proposition

Clearly state and label (as a proposition P(n)).

- the proposition you are trying to prove

- the basis step

- the inductive step (describe this in words)

Show that the basis step is correct. Then prove the inductive step and state the conclusion by applying mathematical deduction. Make sure you show all steps and that your proof begins from valid premises and proceed logically.

B. Prove that any combination of postage greater than 7 cents can be made using some combination of 3 cent and 5 cent stamps.

Solution

B. Prove that any combination of postage greater than 7 cents can be made using some combination of 3 cent and 5 cent stamps

P(n) is the statement that for any n >7, combination of postage can be made using 3 and 5 cent stamps.

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

For induction proof, we verify P(1), assume P(K) and derive P(k+1) from P(K) assumption.

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

Let n =8.

1 5 stamp and 1 3 stamp will make 8.

Hence true for n =8

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

Assume P(K) is true.

i.e. k = 3l+5m for some integer l and m. (Then only combination can be made)

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

Consider k+1 = 3l+5m+1

1= 2(5) -3(3)

Hence k+1 = 3l+5m+2(5)-3(3)

= 3(l-3) +5(m-2) where l-3 and m-2 are integers.

Hence P(K+1) is true.

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

Thus proved for induction for all natural numbers n.