Recurrence relations question

Question

A vending machine dispensing books of stamps accepts only one-dollar coins, $1 bills, and $5 bills.

a) Find a recurrence relation for the number of ways to deposit $n$ dollars in the vending machine, where the order in which the coins and bills are deposited matters.

b) What are the initial conditions ?

c) How many ways are there to deposit $10 for a book of stamps ?

Answer 1

When you deposit $n$\$ you either :

• deposit 1\$ coin, and then deposit $n-1$\$
• deposit 1\$ bill, and then deposit $n-1$\$
• deposit 5\$ bill, and then deposit $n-5$\$ (if $n\ge 5$)

Hence $$f_n=2f_{n-1}+f_{n-5} $$

Initial condition : $f_0=1$ (one way to deposit nothing, by doing nothing).

\begin{array}{ccccccccccc} n&0&1&2&3&4&5&6&7&8&9&10\\ f_n&1&2&4&8&16&33&68&140&288&592&1217\\ \end{array}