I have a question regarding the solution of this problem.

The problem is:

Suppose that we have n dollars to use to buy either orange juice for 1, milk for 2, or beer for 2, and the order in which we make the purchases matter. Let $R_n$ be the number of ways to spend all the money. Derive a recurrence relation and initial conditions for the sequence $R_0$, $R_1$, $R_2$, ... .

The solution is: $R_n$ = $R_{n-1}$ + 2$R_{n-2}$, with $R_0$ = 1 and $R_1$ = 1.

Now I understand how to get the recurrence relation, and I understand the initial condition for $R_1$=1, but I don't understand why $R_0$ = 1 as well. If you have n = 0, which represents 0 dollars, shouldn't you have 0 ways to spend it?



We clearly have $\;R_1=1\;,\;\;R_2=3\;$ , so we get $\;R_0\;$ from the recursive relation:

$$3=R_2=R_1+2R_0=1+2R_0\implies R_0=1$$

Many times $\;R_0\;$ doesn't have an intuitive meaning connected with the problem, is just something helpful to make work the recursion

  • $\begingroup$ Thanks! It makes sense now :) $\endgroup$ – King Tut Feb 22 '16 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.