• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q4E

Expert-verified
Found in: Page 341

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Let ${\mathbit{P}}{\mathbf{\left(}}{\mathbit{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 ${\mathbit{P}}{\mathbf{\left(}}{\mathbit{n}}{\mathbf{\right)}}$ is true for ${\mathbit{n}}{\mathbf{\ge }}{\mathbf{18}}$ .(a) Show statements ${\mathbit{P}}{\mathbf{\left(}}{\mathbf{18}}{\mathbf{\right)}}{\mathbf{,}}{\mathbit{P}}{\mathbf{\left(}}{\mathbf{19}}{\mathbf{\right)}}{\mathbf{,}}{\mathbit{P}}{\mathbf{\left(}}{\mathbf{20}}{\mathbf{\right)}}$ and ${\mathbit{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 ${\mathbit{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.

See the step by step solution

## Step 1: Given that

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)

## Step 2: Show that P(18) is true

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.

## Step 3: Show that P(19) 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.

## Step 4: Show that P(20) 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.

## Step 5: Show that P(21) 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)

## Step 6: State inductive hypothesis

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)

## Step 7: Proof needed in inductive step

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)

## Step 8: Inductive step for k≥21

We want to form $k+1$ cents of postage. Since $k\ge 21$, it is clear that $P\left(k-3\right)$ 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$ .

## (e)Step 9: Explanation

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.