Question

a) Which amounts of postage can be formed using only 5-cent and 9-cent stamps?

b) Prove the conjecture you made using mathematical induction.

c) Prove the conjecture you made using strong induction.

d) Find proof of your conjecture different from the ones you gave in (b) and (c).

Short answer

a) 0,5,9,10,14,15,19,20,23,24,25,27,28,29,30 and all amount greater than or equal to \(32{\rm{ cent}}\)

b) Replace seven of the \({\rm{5 - cent}}\) stamps with four \(9 - cent\)stamps.

c) 0 achieve \(n - cents\)postage, take the stamps used for \(n - 5{\rm{ }}cent\) and adjoin.

d) Use the quotient remainder of the theorem.

Step-by-step solution

Mathematical Induction.

To prove that \(p\left( n \right)\) is true for all positive integers\(n\), where \(p\left( n \right)\) is a propositional function, we complete two steps.

Basis step: - We verify that\(p\left( 1 \right)\)is true.

Inductive step: We show the conditional statement\(p\left( k \right) \to p\left( {k + 1} \right)\) is true for all positive integers\(k\).

Strong Induction.

To prove that\(p\left( n \right)\)holds for all positive integers n, where\(p\left( n \right)\)is a propositional function, we perform two steps.

Basis step: - We verify that the proposition\(p\left( 1 \right)\)is true.

Inductive Step:-We show the conditional statement,

\(\left( {p\left( 1 \right) \wedge p\left( 2 \right) \wedge ....... \wedge p\left( K \right)} \right) \to p\left( {k + 1} \right)\) is true for all positive integer k.

a) Can be formed using only 5-cent and 9-cent stamps.

1) Solution.

Here carefully consider all the possibilities of postage less than\(32{\rm{ Cents}}\).

\({\rm{0,5,9,10,14,15,18,19,20,23,24,27,28,29 and 30}}{\rm{.}}\)

All amounts greater than or equal to\(32{\rm{ Cents}}\).

b) Prove the conjecture you made using mathematical induction.

1).

Here check the basis step\(32 = 9 + 9 + 9 + 5\).

2).

Here assume that can achieve\(n + 1{\rm{ cents}}\), where\({\rm{n}} \sim {\rm{32}}\).

If the stamps used \(n - cents\)include a \(9 - cents\)stamp, then replacing it with two \(5 - cent\) stamps gives us\(n + 1{\rm{ }}cent\).as desired.

Otherwise only\(5 - cent\) stamps were used to achieve \(n\)cents.

Since\(n > 30\)must be at least seven such stamps.

Here replace seven of the \(5 - cent\) stamps with four \(9 - cent\) stamps.

This increases the amount of, postage by, again as desired.

c) Prove the conjecture you made using strong induction.

Here check the base case:-

\(\begin{aligned}{l}32 = 3.9 + 5\\33 = 2.9 + 3.5\\34 = 9 + 5.5\\35 = 7.5\\36 = 4.9\end{aligned}\)

Here fix \(n\)and assume all amounts form \({\rm{32}}\) to be found.

To find \(n{\rm{ cents}}\)postage and adjoin a\({\rm{n - 5 cents }}\).

d) Find proof of your conjecture different from the ones you gave in (b) and (c).

1).

Let \(n{\rm{ }}\) be an integer greater than or equal to\(32\).

Here express \(n\)as a sum of a nonnegative multiple of 5 and a nonnegative multiple of 9.

2).

Divide \(n\)by 5 to obtain a quotient. \({\rm{q}}\) and remainder\({\rm{r}}\).

Such that\({\rm{n = 5q + r}}\).

Note that since\({\rm{n}} \sim {\rm{32}}\)\({{\rm{q}}_2}6\).

If\(r = 0\), then we already have \({\rm{n}}\)expressed in the desired form.

If\(r = 1\), then \({n_2}36\) so \({q_2}7\).this we can write,

\(\begin{aligned}{c}n = 5q + 1\\ = 5\left( {q - 7} \right) + 4.9\end{aligned}\)

To get the desired decomposition,

If\(r = 2\), then we rewrite

\(\begin{aligned}{c}n = 5q + 2\\ = 5\left( {q - 5} \right) + 3.9\end{aligned}\)

If\(r = 3\), then we rewrite,

\(\begin{aligned}{c}n = 5q + 3\\ = 5\left( {q - 3} \right) + 2.9\end{aligned}\)

And if\(r = 4\), then we rewrite,

\(\begin{aligned}{c}n = 5q + 4\\ = 5\left( {q - 1} \right) + 9\end{aligned}\).

In each case, we have the desired sum.