A vending machine dispensing books of stamps accepts only $1 coins, $1 bills, and $2 bills. Let an denote the
number of ways of depositing n dollars in the vending machine, where the order in which the coins and bills
are deposited matters.
(a) Find a recurrence relation for an and give the necessary initial condition(s).
(b) Find an explicit formula for an by solving the recurrence relation in part (a).

Question

Quizplus · Accepted Answer

The Answer is (a)

a _ { n } = 2 a _ { n - 1 } + a _ { n - 2 } , a _ { 0 } = 1 , a _ { 1 } = 2

.
(b)

a _ { n } = \alpha ( 1 + \sqrt { 2 } ) ^ { n } + \beta ( 1 - \sqrt { 2 } ) ^ { n }

where

\alpha = \left( 1 + \frac { 1 } { \sqrt { 2 } } \right) / 2

and

\beta = \left( 1 - \frac { 1 } { \sqrt { 2 } } \right) / 2

A Vending Machine Dispensing Books of Stamps Accepts Only $1