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. 


Let's tackle it the general way. Define the ordinary generating function:
$$
T(z)  = \sum_{n \ge 0} t_n z^n
$$
Writing the recurrence as $t_{n + 4} = t_{n + 3} + t_{n + 1} - t_n$,
the properties of ordinary generating functions give:
$$
\begin{align*}
\frac{T(z) - t_0 - t_1 z - t_2 z^2 - t_3 z^3}{z^4}
  &= \frac{T(z) - t_0 - t_1 z - t_2 z^2}{z^3} 
       + \frac{T(z) - t_0}{z} - T(z) \\
T(z) &= \frac{z}{(1 - z)^2}
\end{align*}
$$
This has the coefficient:
$$
t_n = [z^n] \frac{z}{(1 - z)^2}
    = [z^{n - 1}] \frac{1}{(1 - z)^2}
    = (-1)^{n - 1} \binom{-2}{n - 1}
    = n
$$
