1

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.

user1176409
  • 1
user142743
  • 127
  • Have you tried working out the number of ways to spend 2 dollars? Doing that might give you some ideas about how the recurrence works. – MJD May 10 '14 at 04:43
  • A problem of a very similar flavour was asked and answered recently. The same sort of analysis will work. This problem is somewhat simpler than the previous one. – André Nicolas May 10 '14 at 04:51

1 Answers1

0

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}\;. $$

joriki
  • 238,052