Recurrence relations 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 ?

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}