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

Q4E

Expert-verifiedFound in: Page 341

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Let ${\mathit{P}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}$ be the statement that a postage of n cents can be formed using 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that ${\mathit{P}}{\mathbf{\left(}}{\mathit{n}}{\mathbf{\right)}}$ is true for ${\mathit{n}}{\mathbf{\ge}}{\mathbf{18}}$ .**

**(a) Show statements ${\mathit{P}}{\mathbf{\left(}}{\mathbf{18}}{\mathbf{\right)}}{\mathbf{,}}{\mathit{P}}{\mathbf{\left(}}{\mathbf{19}}{\mathbf{\right)}}{\mathbf{,}}{\mathit{P}}{\mathbf{\left(}}{\mathbf{20}}{\mathbf{\right)}}$ and ${\mathit{P}}{\left(32\right)}$ are true, completing the basis step of the proof.**

**(b) What is the inductive hypothesis of the proof?**

**(c) What do you need to prove in this inductive step?**

**(d) Complete the inductive step for ${\mathit{k}}{\mathbf{\ge}}{\mathbf{21}}$ .**

**(e) Explain why these steps show that statement is true whenever **

(a) It has been proved that the statements $P\left(18\right),P\left(19\right),P\left(20\right)$ and $P\left(21\right)$ are true.

(b) The inductive hypothesis is explained.

(c) The proof is explained.

(d) The steps are completed.

(e) The reason is explained.

Given that $P\left(n\right)$ be the statement that a postage of *n* cents can be formed using 4-cent stamps and 7-cent stamps.

**(a)**

For $n=18$

Take 1 4-cent stamps and 2 7-cent stamps.

2 7-cent stamps = 14 cents

1 4-cent stamp = 4 cents.

Total = 18 cents.

Therefore, 18 cents of postage can be formed using 4-cent stamps and 7-cent stamps.

Hence, $P\left(18\right)$ is true.

For $n=19$

Take 3 4-cent stamps and 1 7-cent stamps.

1 7-cent stamps = 7 cents

3 4-cent stamp = 12 cents.

Total = 19 cents.

Therefore, 19 cents can be formed using 4-cent stamps and 7-cent stamps.

Hence, $P\left(19\right)$ is true.

For $n=20$

Take 5 4-cent stamps and zero 7-cent stamps.

5 7-cent stamps = 20 cents

0 4-cent stamp = 0 cents.

Total = 20 cents.

Therefore, 20 cents can be formed using 4-cent stamps and 7-cent stamps.

Hence, $P\left(20\right)$ is true.

For $n=21$

Take 0 4-cent stamps and 3 7-cent stamps.

3 7-cent stamps = 21 cents

0 4-cent stamp = 0 cents.

Total = 21 cents.

Therefore, 21 cents can be formed using 4-cent stamps and 7-cent stamps.

Hence, $P\left(21\right)$ is true.

**(b)**

The inductive hypothesis is the statement that using just 4-cent and 7-cent stamps we can form j cents postage for all j with $18\le j\le k$ .

**(c)**

In the inductive step we must show, assuming the inductive hypothesis, that we can form $k+1$ cents postage using just 4-cent and 7-cent stamps.

**(d)**

We want to form $k+1$ cents of postage. Since $k\ge 21$, it is clear that $P(k-3)$ is true, that is, $k-3$ cents of postage can be formed.

By putting one more 4-cent stamp on the envelope, $k+1$ stamp postage can be formed

Hence, inductive step is true for$k\ge 21$ .

Since both the basis step and inductive steps are completed, By the Principal of strong induction. Statement is true for every integer *n* greater than or equal to 18.

94% of StudySmarter users get better grades.

Sign up for free