A bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into the mechanical toll collector. a) Find a recurrence relation for the number of different ways the bus driver can pay a toll of n cents (where the order in which the coins are used matters). b) In how many different ways can the driver pay a toll of 45 cents.

Answer: a) An = An-1 + An-2b) 55waysStep-by-step explanation:a) a nickel is 5 cents and a dime is 10cent so a multiple of 5 cents is the possible way to pay the tolls in both choices.Let An represents the number of possible ways the driver can pay a toll of 5n cents, so thatAn = 5n centsCase 1: Using a nickel for payment which is 5 cents, the number of ways given as;An-1 = 5( n-1)Case 2: using a dime which is two 5 cents, the number of ways is given as;An-2 = 5(n-2)Summing up the number of ways, we haveAn = An-1 + An-2From the relation,If n= 0, Ao= 1 n =1, A1= 1 b) 45 cents paid in multiples of 5cents will give us 9 ways(A9)From the relation, we have thatAo = 1A1 = 1An =An-1 + An-2Ao = 1A1 = 1A2 = A1+Ao = 1+1= 2A3 = A2 + A1 = 3A4 = A3+A2=5A5=A4+A3=8A6=A5+A4=13A7 =A6+A5 = 21A8= A7+A6= 34A9= A8+A7= 55So there are 55ways to pay 45cents.