Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

Let $P (n)$ 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 $P (n)$ is true for $n \geq 18$ .
(a) Show statements $P (18), P (19), P (20)$ and $P (32)$ 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 $k \geq 21$ .
(e) Explain why these steps show that statement is true whenever

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

(b) The inductive hypothesis is explained.

(d) The steps are completed.

(e) The reason is explained.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Given that

Given that $P (n)$ 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 (18)$ 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 (19)$ 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 (20)$ 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 (21)$ 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 \leq j \leq 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 \geq 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 \geq 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.

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Given that

Step 2: Show that P(18) is true

Step 3: Show that P(19) is true

Step 4: Show that P(20) is true

Step 5: Show that P(21) is true

Step 6: State inductive hypothesis

Step 7: Proof needed in inductive step

Step 8: Inductive step for k≥21

(e)Step 9: Explanation

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

Step by Step Solution

Step 1: Given that

Step 2: Show that P(18) is true

Step 3: Show that P(19) is true

Step 4: Show that P(20) is true

Step 5: Show that P(21) is true

Step 6: State inductive hypothesis

Step 7: Proof needed in inductive step

Step 8: Inductive step for k≥21

(e)Step 9: Explanation

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths