7.1 / #36
a) Say there are a_n ways to pay a toll of n cents. Since order matters, let us look at the last coin that is used to pay the n cents. It can be either a nickel or a dime. If it is a nickel, there are a_(n-5) ways to pay the toll, since the nickel accounts for 5 cents of the n and we can therefore divide the remaining n-5 cents in any way. If it is a dime, there are a_(n-10) ways by the same reasoning. Thus, our recursive relation is a_n = a_(n-5)+a_(n-10)
b) Simply apply the recursion until a_45. The initial conditions are: a_5 = 1 (since you can only pay that with a nickel) a_10 = 2 (nickel-nickel or just one dime) a_15 = 1 + 2 = 3 a_20 = 3 + 2 = 5 a_25 = 5 + 3 = 8 a_30 = 8 + 5 = 13 a_35 = 13 + 8 = 21 a_40 = 21 + 13 = 34 a_45 = 34 + 21 = 55
