Let Pn be any collection of n coins can be obtained using a

Let P(n) be “any collection of n coins can be obtained using a combination of 3c/ and 5c/ coins.” Use strong mathematical induction to prove that P(n) is true for all integers n 14.

Solution

14 = 3*3 + 5*1

=>

the statment is true for n = 14

let the statement be true for n = k

=>

k = 3a +5b, for some integers a,b>0

case 1: k is a multiple of 3, i.e k = 3a

since k>=14, a>=5

k+1 = 3a +1 = 3a + 5*(2) -3*3 = 3(a-3) +5*2

=>

k+1 = 3(a-3) =5*2

case 2: k is not a multiple of 3 ,i.e b>0

k = 3a+5b

=>

k+1 = 3a +5b +1 = 3a +5b + 3(2) -5 = 3(a+2) + 5(b-1)

k+1 = 3(a+2) +5(b-1)

=>

the statement is true for n = k+1

thus proved by induction