Number of ways 1a,1b,5 can add up to n (with this being a permutation)

Question

This problem is on my homework.

A vending machine dispensing books of stamps accepts $\$ $ 1 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.

The book says the recurrent relation is $ a_n = 2a_{n-1}+a_{n-5}$ for $ n \ge 5 $ which is the ultimate answer to the question, but I am stuck on the middle which is figuring the iterations.

So based on the recurrent relation these are the answers $a_0 = 1$, $a_1 = 2$, $a_2 = 4$, $a_3 = 8$, $a_4 = 16$, $a_5 = 33$, $a_6 = 68$, $a_7 = 140$, $a_8 = 288$, $n_9 = 592$

How can I find the number of permutations? for example I would think

$a_7 = 2^7+ 2^3$ but that equals $136$ not $140$

Answer 1

First you need to build the recurrence relation and then you need to solve that.

Recurrence relation:

Let $a_n$ be the number of ways to dispense $\$n$ using the given currencies. To pay $\$n$ exactly one of the following should happen:

1. Suppose $\$n-1$ have been paid then to pay the total amount $\$n$, the last denomination used can be $\$1$ coin.
2. Suppose $\$n-1$ have been paid then to pay the total amount $\$n$, the last denomination used can be $\$1$ bill.
3. Suppose $\$n-5$ have been paid then to pay the total amount $\$n$, the last denomination used can be $\$5$ bill.

The number of ways in which the first two cases can happen is $a_{n-1}$ and the number of ways in which the last case can happen is $a_{n-5}$. Thus $$a_n=2a_{n-1}+a_{n-5}.$$

Solving the recurrence relation:

Let us assume that the solution is of the form $a_n=r^n$. Then substituting this into the recurrence relation yields: $$r^{n}=2r^{n-1}+r^{n-5}.$$ This results in: $$r^5=2r^{4}+1.$$ Now solutions to this will help you construct the closed form of $a_n$.