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 an=an−5+an−10a_n = a_{n-5} + a_{n-10} With the base cases being a0=1a_0 = 1 and a5=1a_5 = 1. Could someone help clarify why this is the solution? I understand the second base case. a5=1a_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?

=================

As to the recursion: the last coin is either a nickel or a dime. If a nickel, then the fellow must have gotten to an−5a_{n-5} first. If a dime, then he must have reached an−10a_{n-10} and used a dime.

– lulu

Oct 20 at 19:32

If you don’t like a0=5a_0=5 (which just means “there is only one way to put no coins in a row”) then use a10=2a_{10}=2 instead.

– lulu

Oct 20 at 19:34

@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?

– foobar512

Oct 20 at 19:35

Well…recursions generally try to build from smaller values to greater, this is just a way to do that.

– lulu

Oct 20 at 19:36

=================

=================