A student visits an ice cream store once a day. During each visit he buys either a banana split for three dollars or a frozen yogurt in one of two possible flavors for two dollars. Find a recurrence relation for the number of ways, to spend n dollars at the ice cream store.
I know this problem is with using recurrence but not sure how would I approach this problem.
Let $a_n$ be the number of ways to spend $n$ dollars. For $n\gt 3$, we have $a_n=2a_{n-2}+a_{n-3}$. Suitable initial conditions are $a_1=0$, $a_2=2$, $a_3=1$.
Justification: How many ways can we reach a total expenditure of $n$ dollars? Either (i) the last sugar-bomb we buy to reach $n$ dollars is a frozen yogurt or (ii) it is a banana split.
In Case (i), before the frozen yogurt, we had spent a total of $n-2$ dollars. By definition, this can be done in $a_{n-2}$ ways. For each of these ways, there are $2$ ways to choose the frogen yogurt, for a total contribution of $2a_{n-2}$.
In Case (ii), before the banana split, we had spent $n-3$ dollars, and this can be done in $a_{n-3}$ ways.
So we can reach a total expenditure of $n$ in $2a_{n-2}+a_{n-3}$ ways.
Remark: The above recurrence can be used to quickly compute $a_n$, at least for smallish $n$. We have $a_1=0$ (there is no way to spend $1$ dollar), and $a_2=2$ (either frozen yogurt), and $a_3=1$. Now we compute.
$a_4=2a_2+a_1=4$
$a_5=2a_3+a_2=4$
$a_6=2a_4+a_3=9$
$a_7=2a_5+a_4=12$
$a_8=2a_6+a_5=22$
$a_9=2a_7+a_6=33$
And so on.
