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

(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.

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Given that

Given: 4-cent and 11-cent stamps.

(a)

Step 2: Determine amount of postage that can be formed using 4-cent and 11-cent stamp

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

$4 = 4 8 = 4 + 4 11 = 11$

$12 = 4 + 4 + 4 15 = 11 + 4 16 = 4 + 4 + 4 + 4 19 = 11 + 4 + 4 20 = 4 + 4 + 4 + 4 + 4$

$22 = 11 + 11 23 = 11 + 4 + 4 + 4 24 = 4 + 4 + 4 + 4 + 4 + 4 26 = 11 + 11 + 4 27 = 11 + 4 + 4 + 4 + 4 28 = 4 + 4 + 4 + 4 + 4 + 4 + 4 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)

Step 3: Prove using principle of mathematical induction

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

To prove: The statement is true for all $n \geq 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 \geq 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)

Step 4: Proof using strong induction

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

To prove: The statement is true for all $n \geq 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 (j)$ is true for all j with $30 \leq j \leq 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 \geq 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.

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: Determine amount of postage that can be formed using 4-cent and 11-cent stamp

Step 3: Prove using principle of mathematical induction

Step 4: Proof using strong induction

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: Determine amount of postage that can be formed using 4-cent and 11-cent stamp

Step 3: Prove using principle of mathematical induction

Step 4: Proof using strong induction

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