Consider the following:

A bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into the mechanical toll collector. 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).

The solution is $a_n = a_{n-5} + a_{n-10}$ With the base cases being $a_0 = 1$ and $a_5 = 1$. Could someone help clarify why this is the solution? I understand the second base case. $a_5 = 1$ because there is 1 way to pay a 5 cent toll. But I don't understand the first base case or the relation itself. What process can I follow to solve this word problem as well as others?

  • $\begingroup$ As to the recursion: the last coin is either a nickel or a dime. If a nickel, then the fellow must have gotten to $a_{n-5}$ first. If a dime, then he must have reached $a_{n-10}$ and used a dime. $\endgroup$ – lulu Oct 20 '16 at 19:32
  • $\begingroup$ If you don't like $a_0=5$ (which just means "there is only one way to put no coins in a row") then use $a_{10}=2$ instead. $\endgroup$ – lulu Oct 20 '16 at 19:34
  • $\begingroup$ @lulu I understand the other base case now, thanks. But I'm still a little confused on the recurrence relation, why look at the last coin the first place? $\endgroup$ – foobar512 Oct 20 '16 at 19:35
  • $\begingroup$ Well...recursions generally try to build from smaller values to greater, this is just a way to do that. $\endgroup$ – lulu Oct 20 '16 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.