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

### Select your language

Suggested languages for you:

Americas

Europe

Q5E

Expert-verified
Found in: Page 342

### Discrete Mathematics and its Applications

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.

See the step by step solution

## 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\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)

## Step 3: Prove using principle of mathematical induction

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)

## Step 4: Proof using strong induction

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\left(k+1\right)$ is true.

Proof: Since $k-3\ge 30$, so $P\left(k-3\right)$ 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\left(k+1\right)$ is true.

Hence, the statement is true.