Purchasing Order: An Analysis on A ($\textrm{C++}$)-Approached Recurrence Relation 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 );

}

 A: 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}$$
A: 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.
