Finding the recurrence relation for number of ways to deposit n dollars

Question

Question: A vending machine dispensing books of stamps accepts only one dollar coins, 1 dollar bills and 5 dollar 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 initial conditions?

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

My Answers: a) For $a_0$, there is 0 ways to deposit 0 dollars in the machine because since it is 0 dollars, you cannot put in any money to come up with that value. So, $a_0$= 0

For $a_1$, there are 2 ways, you can put in 1 of one dollars coins and 1 of one dollar bill. So $a_1$ = 2.

For $a_2$, there are 3 ways, you can put in 2 of 1 dollar bill, 2 of 1 dollar coin and 1 of dollar coin and 1 dollar bill. So $a_2$ = 3.

b) Initial condition would be starting with $a_0 $= 0.

Answer 1

There's one way to put \$0 in, two ways to add another \$1, and one way to add another \$5, so:

$f(n)=\begin{cases} &1&n = 0\\ &2 \cdot f(n-1)&1 \le n \le 4\\ &2 \cdot f(n-1) + f(n-5)&5 \le n \end{cases}$

$\{f(i)\}=\{1,2,4,8,16,33,68,140,288,592,...\}$

Answer 2

Dirty trick: Use generating functions. As the order in which the money is deposited matters, exponential generating functions are appropiate.

For \$1.- coins, the generating function is just: $$ 1 + \frac{z}{1!} + \frac{z^2}{2!} + \ldots = \mathrm{e}^z $$ Ditto for \$1.- bills. Up to here this tells us that the way of inserting \$$n$ in coins or bills is: $$ n! [z^n] \mathrm{e}^z \cdot \mathrm{e}^z = n! [z^n] \mathrm{e}^{2 z} = 2^n $$ Just as was to be expected, each of the $n$ dollars can be independently selected as a coin or a bill.

For \$5.- dollar bills you have: $$ 1 + \frac{z^5}{1!} + \frac{z^{10}}{2!} + \ldots = \mathrm{e}^{z^5} $$ So we get the (not so) pleasant result for the generating function for the number of ways of depositing \$$n$: \begin{align} \mathrm{e}^{2 z + z^5} &= \sum_{r \ge 0} \frac{(2 z + z^5)^r}{r!} \\ &= \sum_{r \ge 0} \frac{1}{r!} \left( \sum_{0 \le s \le r} \binom{r}{s} 2^r z^{r + 5 (r - s)} \right) \\ &= \sum_{r \ge 0} \frac{1}{r!} \left( \sum_{0 \le s \le r} \binom{r}{s} 2^r z^{6 r - 5 s} \right) \end{align} It is possible to get a (messy) result for the terms out of this.