Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation

Question

Suppose that we have $n$ dollars and that each day we buy either tape at a dollar, paper at a dollar, pens at two dollars, pencils at two dollars, or binders at three dollars. If $R_n$ is the number of ways of spending all the money, derive a recurrence relations for the sequence $R_1$, $R_2$, $\dots$

---

Just as an aside, for anybody here who has some experience with $\textrm C{+}{+}$ perhaps it would be enlightening to teach this as a recursive algorithm, as, for example with this algorithm I made for this problem:

int S( int n ){

if( n == 0 )
    return 1;
if( n == 1 )
    return 2;
if( n == 2 )
    return 4;
if( n == 3 )
    return 7;
return 2*S( n - 2 ) + S( n - 1 );

}

Answer 1

There are exactly $3$ exhaustive and mutually exclusive ways to make your first purchase.

Case 1: Suppose you spend $1$ dollar by buying either the tape or paper first. This can be done in $2$ ways. After doing this, there are $R_{n-1}$ ways to spend the remaining $n-1$ dollars.

Case 2: Suppose you spend $2$ dollars by buying either the pens or pencils first. This can be done in $2$ ways. After doing this, there are $R_{n-2}$ ways to spend the remaining $n-2$ dollars.

Case 3: Suppose you spend $3$ dollars by buying the binders first. This can be done in $1$ way. After doing this, there are $R_{n-3}$ ways to spend the remaining $n-3$ dollars.

Putting everything together (and after working out some base cases), we obtain: $$ R_n=\begin{cases} 2 & \text{if }n=1 \\ 6 & \text{if }n=2 \\ 21 & \text{if }n=3 \\ 2R_{n-1}+2R_{n-2}+R_{n-3} & \text{if }n\geq4 \\ \end{cases}$$

Answer 2

The mathematician's way is to use generating functions: $$\sum_{i=0}^\infty R_iz^i = \sum_{k=0}^\infty (2z+2z^2+z^3)^k =\frac{1}{1-2z-2z^2-z^3}$$ Unfortunately, the roots of $1-2z-2z^2-z^3$ are non-trivial, but the sequence $R_n\sim cr^n$ where $c$ is a some constant and $r\approx 2.8312$ is the real root of $x^3-2x^2-2x-1$. (It's actually stronger than this - more like $|R_n-cr^n|\to 0$ since the complex roots are of modulus less than $1$.)

You also get from this equation that $R_{n+3} = 2R_{n+2}+2R_{n+1}+R_n$, which is sort of obvious.