Solve $t_{n}=t_{n-1}+t_{n-3}-t_{n-4}$? I missed the lectures on how to solve this, and it's really kicking my butt. Could you help me out with solving this? 

Solve the following recurrence exactly.
  $$
t_n = \begin{cases}
n, &\text{if } n=0,1,2,3,
\\ t_{n-1}+t_{n-3}-t_{n-4}, &\text{otherwise.}
\end{cases}
$$
  Express your answer as simply as possible using the $\Theta$ notation. 


Hint: 
Write $t_n = r^n$, substitute into the definition of $t_n$ for $n>3$ and solve for $r$. You will find four possible solutions. Call them $r_1$, $r_2$, $r_3$ and $r_4$. Because the defining equation is linear, you can write
$$t_n = A r_1^n + B r_2^n + C r_3^n + D r_4^n$$
Now how can you work out what the constants $A$, $B$, $C$, $D$ are?
