Use mathematical induction (and the proof of Proposition

Chapter 5, Problem 1E

(choose chapter or problem)

Problem 1E

Use mathematical induction (and the proof of Proposition as a model) to show that any amount of money of at least 14c can be made up using 3¢ and 8¢ coins.

Proposition

For all integers n ≥ 8, n¢ can be obtained using 3¢ and ¢ coins.

Proof (by mathematical induction):

Let the property P(n) be the sentence

n¢ can be obtained using 3¢ and 5¢coins. ← P(n)

Show that P(8) is true:

P(8) is true because 8¢can be obtained using one 3¢coin and one 5¢ coin.

Show that for all integers k≥ 8, if P(k) is true then P(k+1) is also true:

[Suppose that P(k) is true for a particular but arbitrarily chosen integer k ≥ 8. That is:]

Suppose that k is any integer with k ≥ 8 such that

k¢ can be obtained using 3¢ and 5¢ coins. ← P(k) inductive hypothesis

[We must show that P(k + 1) is true. That is:] We must show that

(k + 1)¢can be obtained using 3¢ and 5¢ coins. ← P(k + 1)

Case 1 (There is a 5¢ coin among those used to make up the k¢.): In this case replace the 5¢ coin by two 3¢ coins; the result will be (k + 1) ¢.

Case 2 (There is not a 5¢ coin among those used to make up the k¢.): In this case, because k ≥ 8, at least three 3¢ coins must have been used. So remove three 3¢ coins and replace them by two 5¢ coins; the result will be (k + 1) ¢.

Thus in either case (k + 1) ¢ can be obtained using 3¢ and 5¢ coins [as was to be shown].

[Since we have proved the basis step and the inductive step, we conclude that the proposition is true.]

Unfortunately, we don't have that question answered yet. But you can get it answered in just 5 hours by Logging in or Becoming a subscriber.

Becoming a subscriber
Or look for another answer

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back