Finding the recurrence relation for number of ways to deposit n dollars 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.
 A: 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,...\}$
A: 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.
