StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q5E

Expert-verifiedFound in: Page 342

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**(a) Determine which amounts of postage can be formed using just 4-cent and 11-cent stamps.**

**(b) Prove your answer to (a) using the principle of mathematical induction. Be sure to state explicitly your inductive hypothesis in the inductive step.**

**(c) Prove your answer to (a) using strong induction. How does the inductive hypothesis in this proof differ from that in the inductive hypothesis for a proof using mathematical induction?**

(a) All the amounts of postage that can be formed are determined.

(b) Prove is done using principle of mathematical induction.

(c) Prove is done using strong induction.

Given: 4-cent and 11-cent stamps.

**(a)**

Using 4-cent and 11-cent stamps, following amount of postage can be formed:

$4=4\phantom{\rule{0ex}{0ex}}8=4+4\phantom{\rule{0ex}{0ex}}11=11$

$12=4+4+4\phantom{\rule{0ex}{0ex}}15=11+4\phantom{\rule{0ex}{0ex}}16=4+4+4+4\phantom{\rule{0ex}{0ex}}19=11+4+4\phantom{\rule{0ex}{0ex}}20=4+4+4+4+4$

$22=11+11\phantom{\rule{0ex}{0ex}}23=11+4+4+4\phantom{\rule{0ex}{0ex}}24=4+4+4+4+4+4\phantom{\rule{0ex}{0ex}}26=11+11+4\phantom{\rule{0ex}{0ex}}27=11+4+4+4+4\phantom{\rule{0ex}{0ex}}28=4+4+4+4+4+4+4\phantom{\rule{0ex}{0ex}}30=11+11+4+4$

The gaps between the above lists cannot be filled.

__Claim:__ All amount of postage greater than or equal to 30 cents can be formed using just 4-cent and 11-cent stamps

**(b)**

Let $P\left(n\right):$ n cents of postage can be formed using just 4-cents and 11-cents stamps.

To prove: The statement is true for all $n\ge 30$.

The basis step: The statement is true for $n=30$

Inductive hypothesis: Assume that the statement is true for $n=k$, that is, *k* cents of postage can be formed using 4-cents and 11-cents stamps.

To show: The statement is true for $k+1$ cents of postage.

Proof: If *k* cents includes an 11-cent stamps, the it can be replaced by three 4-cent stamps. ($11+1=4+4+4$).

Otherwise, *k* cents was formed either from just 4-cent stamps.

Because $k\ge 30$, there must be at least 8 4-cent stamps involved in either of the case.

Replace eight 4-cent stamps by three 11-cent stamp and $k+1$ cents postage are formed.

Hence, the statement is true for $n=k+1$ whenever it is true for $n=k$ .

**(c)**

Let $P\left(n\right):$ n cents of postage can be formed using just 4-cents and 11-cents stamps.

To prove: The statement is true for all $n\ge 30$ .

The basis step: The statement is true for $n=30,31,32,33$ (as done in part (a))

Inductive hypothesis: Assume that the statement $P\left(j\right)$ is true for all j with $30\le j\le k$, where *k* is a fixed integer greater than or equal to 33.

To show: The statement $P(k+1)$ is true.

Proof: Since $k-3\ge 30$, so $P(k-3)$ is true that is postage stamps can be formed.

By putting one more 4-cent stamp, postage stamp can also be formed.

This implies $P(k+1)$ is true.

Hence, the statement is true.

94% of StudySmarter users get better grades.

Sign up for free