A man visits a pastry shop each morning. During each visit he buys either one of two types of pastry costing one dollar each or one of three types of pastry costing two dollars each. Find and solve a recurrence relation for the number of ways to spend n dollars at the pastry shop (the order of the purchases matters).
I know this problem has to do with recurrence . In this particular problem I'm not sure how to find the recurrence relation of n dollars.
You can spend $n$ dollars either by first spending $n-1$ dollars and then spending $1$ dollar in one of $2$ ways, or by first spending $n-2$ dollars and then spending $2$ dollars in one of $3$ ways. Thus the number $a_n$ of ways to spend $n$ dollars satisfies
$$ a_n=2a_{n-1}+3a_{n-2}\;. $$