Use mathematical induction to show that change of at least 14c can be obtained using 3c and 8c coins. Show at least from 14c to 27c

Tutors, sign in to answer this question.

Let's first write down the first few decompositions to see the pattern:

14 = 2(3)+1(8) 21 = 7(3)

15 = 5(3) 22 = 2(3)+2(8)

16 = 2(8) 23 = 5(3)+1(8)

17 = 3(3)+1(8) 24 = 8(3)

18 = 6(3) 25 = 3(3)+2(8)

19 = 1(3)+2(8) 26 = 6(3)+1(8)

20 = 4(3)+1(8) 27 = 9(3)

As you can see, each decomposition contains either no 8, one 8, or two 8s, depending on whether the number, or its predecessor, or its successor is divisible by 3. We should base the induction proof on this fact.

Th.: Every integer n≥14 can be decomposed as a sum of 3's and 8's.

Pf. (ind.):

1. The statement is true for n=14, since 14=2(3)+1(8).

2. Assume the statement is true for an arbitrary but fixed n=k+1 (k≥13). We need to show the statement is true for n=k+2.

There are 3 cases:

(i) (k-1) is divisible by 3. Then (k+2) is divisible by 3, and the statement is true.

(ii) k is divisible by 3, i.e., k=3m for some integer m≥4.

Then k+2 = 3m+2 = 3(m-2)+8, and the statement is true.

(iii) (k+1) is divisible by 3, i.e., k+1=3m for some integer m≥5.

Then k+2 = 3m+1 = 3(m-5)+2(8), and the statement is true.

By the principle of induction, the statement is true for all n≥14.

Already have an account? Log in

By signing up, I agree to Wyzant’s terms of use and privacy policy.

Or

To present the tutors that are the best fit for you, we’ll need your ZIP code.

Your Facebook email address is associated with a Wyzant tutor account. Please use a different email address to create a new student account.

Good news! It looks like you already have an account registered with the email address **you provided**.

It looks like this is your first time here. Welcome!

To present the tutors that are the best fit for you, we’ll need your ZIP code.

Please try again, our system had a problem processing your request.