3,794 views
1 votes
1 votes

A vending machine dispensing books of stamps accepts only dollar 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.

b) What are the initial conditions ?

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

Plz tell how to approach this question and solve especially with the Bold part.

2 Answers

1 votes
1 votes

$\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

  1. a one-dollar coin
  2. A $\$1$ bill
  3. 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}$

edited by
1 votes
1 votes
Let a_{n} be the numbers of ways of depositing n dollars

There are 3 ways we can do it

a. depositing $1$ dollar coin and $(n-1)$ dollars left to deposit. So there are $a_{n-1}$ ways to deposit $(n-1)$ dollars

b. depositing $1 bill$ and it is same as depositing $1$dollar coins, so this will also give us $a_{n−1}$ ways to deposit n dollars.

c. deposit a $5 bill$, then we have  $(n − 5)$ dollars left to deposit, so we have $a_{n−5}$ ways to deposit n dollars.

$a_{n} = 2*a_{n-1} + a_{n-5} ( n >= 5 )$

Initial condition

A. only 1 way to deposit 0 dollars(nothing).

B. 1 dollar = 2 ways [ by depositing 1 dollar coin or 1bill]

C. 2 dollar = $2^2$ = 4 ways                        

D. 3 dollar = $2^3$ =  8 ways                                  

E  4 dollar = $2^4$ = 16 ways

$a_{5} = 2*a_{4} + a_{0} = 2*16 + 1 = 33$

$a_{6} = 2*a_{5} + a_{1}= 2*33 + 2 = 68$

$a_{7} = 2*a_{6} + a_{2}= 2*68+ 4 = 140$

$a_{8} = 2*a_{7} + a_{3}= 2*140 + 8 = 288$

$a_{9} = 2*a_{8} + a_{4}= 2*288 + 16 = 592$

$a_{10} = 2*a_{9} + a_{5}= 2*592 + 33 = 1217$
edited by

Related questions

0 votes
0 votes
1 answer
2
admin asked Apr 23, 2020
4,063 views
How many $6$-element RNA sequencesdo not contain U?end with GU?start with C?contain only A or U?
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
aditi19 asked May 13, 2019
630 views
Consider the nonhomogeneous linear recurrence relation $a_n$=$3a_{n-1}$+$2^n$in the book solution is given $a_n$=$-2^{n+1}$but I’m getting $a_n$=$3^{n+1}-2^{n+1}$