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 ?
$\endgroup$1 Answer
$\begingroup$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}
$\endgroup$ 4
