$\color{blue}{\text{Find a recurrence relation for the number of ways to deposit n dollars in the vending machine}}$
Assuming, there are $n$ dollars
So, Number of ways to deposit $n$ dollars will be $a_n$
We can deposit first
only one-dollar coin or $\$1$ bills or $\$5$ bills
∴ We have $3$ choices
- a one-dollar coin
- A $\$1$ bill
- a $\$5$ bill
Now, a one-dollar coin and a $\$1$ bill are same
If we deposit a one-dollar coin or a $\$1$ bill first , then we have $(n-1)$ dollars left to deposit
∴ There will be $a_{(n-1)}$ ways to deposit $n-$dollars
If we deposit a $\$5$ bill first, then we're left with $(n-5)$ dollars to deposit.
∴ We've $a_{(n-5)}$ ways to deposit $n-4 dollars
∴ $a_n = a_{(n-1)}+a_{(n-1)}+a_{(n-5)}$
$a_n = 2a_{(n-1)}+a_{(n-5)}$ applicable if & only if $n\geq 5$, otherwise $a_{n-5}$ makes no sense
$\color{blue}{\text{What are the initial conditions ?}}$
The initial conditions are -
The different ways we can deposit $n$ dollars
{where $n=0$ to $n=4$}
There are only $1$ way to deposit $\$0$ {We didn't insert anything}
∴$a_0=1$
There are $2$ ways to insert $\$1$
{By inserting an $\$1$ or one-dollar coin }
∴$a_1=2$
There are $2^2 =4$ ways to deposit $\$2$
{we have 2 choices by inserting an $\$1$ or one-dollar coin
∴For $\$1$ dollar $\rightarrow 2$ choices
$ \$2$ dollars $\rightarrow 2\times 2 =4 $ choices}
∴$a_2=4$
There are $2^3 =8$ ways to deposit $\$3$
{we have 2 choices by inserting an $\$1$ or one-dollar coin
∴For $\$1$ dollar $\rightarrow 2$ choices
$ \$3$ dollars $\rightarrow 2\times 2 \times 2 =8 $ choices}
∴$a_3=8$
There are $2^4 =16$ ways to deposit $\$4$
{we have 2 choices by inserting an $\$1$ or one-dollar coin
∴For $\$1$ dollar $\rightarrow 2$ choices
$ \$4$ dollars $\rightarrow 2\times 2 \times 2 \times 2 =16 $ choices}
∴$a_4=16$
$\color{blue}{\text{How many ways are there to deposit \$10 for a book of stamps?}}$
∴ $a_{10}=?$
As in a) solution we see that $n$ must be $\geq 5$
∴ We'll start from $a_5$
$a_5 = 2a_4 + a_0 = 2 \times 16 + 1 = 33$
$a_6 = 2a_5 + a_1 = 2 \times 33 + 2 = 68$
$a_7 = 2a_6 + a_2 = 2 \times 68 + 4 = 140$
$a_8 = 2a_7 + a_3 = 2 \times 140 + 8 = 288$
$a_9 = 2a_8 + a_4 = 2 \times 288 + 16 = 592$
$a_10 = 2a_9 + a_5 = 2 \times 592 + 33 = 1217$
∴ $\text{There are 1217 ways to deposit \$10 for a book of stamps}$