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.
Best Answer
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,...\}$