Thread: Strong induction

Suppose that a store offers gift certificates in denominations of 25 dollars and 40 dollars. Determine the possible total amounts that you can form using these gift certificates. Prove your answer using strong induction.

Im stuck on this question, any help would be appreciated.

Thanks

Would this be on the right track?

$25,$40,$50,$75,$80,$100,$120,$125

25x1=25
40x1=40
25x2=50
25x3=75
40x2=80
25x4=100
40x3=120
25x5=125

Continuing the previous comment, you can also get

65 = 40 + 25,
90 = 40 + 2×25,
105 = 2×40 + 25,
130 = 2×40 + 2×25.

You can't get 135, but you can get 140, 145, 150, 155 and 160. Then at that stage the strong induction kicks in (everything up until that point is just the base case). The inductive hypothesis is that you can get all the totals listed so far, together with all multiples of 5 above 160.

The inductive step works because we already have a run of five consecutive multiples of 5 (140, 145, 150, 155 and 160). If n is any multiple of 5 that is greater than 160, then the inductive hypothesis tells you that n-25 is a possible total, from which it obviously follows that n is (by adding one extra $25 certificate).