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

## mathematical induction

Tutors, please sign in to answer this question.

# 1 Answer

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.