solve the following recurrence exactly. $$t(n)=\begin{cases}n&\text{if }n=0,1,2,\text{ or }3\\t(n-1)+t(n-3)+t(n-4)&\text{otherwise.}\end{cases} $$
Express your answer as simply using the theta notation.
I don't know where to go with this.
$$t(n) - t(n-1) - t(n-3) + t(n-4) = 0$$
Is the characteristic polynomial $x^3 - x^2 - x +1 = 0$?
 A: Yes. Note that we find a few obvious factors: 
$$ x^3-x^2-x+1=(x-1)(x^2-1)=(x-1)(x-1)(x+1).$$
A: OK, time to whip out generating functions. Define $T(z) = \sum_{n \ge 0} t(n) z^n$. Take the recurrence written as:
$$
t(n + 4) = t(n + 3) + t(n + 1) + t(n) \qquad t(0) = 0, t(1) = 1, t(2) = 2, t(3) = 3
$$
multiply by $z^n$, add over $n \ge 0$ and express in terms of $T(z)$ do get:
$$
\frac{T(z) - t(0) - t(1) z - t(2) z^2 - t(3) z^3}{z^4}
 = \frac{T(z) - t(0) - t(z) z - t(2) z^2}{z^3}
     + \frac{T(z) - t(0)}{z} + T(z) \\
T(z) = - \frac{2 + z}{5 (1 + z^2)} + \frac{2 + 4 z}{5 (1 - z - z^2)}
$$
The first term is just:
$$
\begin{cases}
- \frac{2}{5} & \text{\(n\) is even} \\
- \frac{1}{5} & \text{\(n\) is odd}
\end{cases}
$$
The second term gives rise to Fibonacci numbers, which have generating function:
$$
F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2} \\
\frac{F(z) - F_0}{z} = \sum_{n \ge 0} F_{n + 1} z^n = \frac{1}{1 - z - z^2}
$$
Pulling all together:
$$
t(n) =
\begin{cases}
- \frac{2}{5} + \frac{2}{5} F_{n + 1} + \frac{4}{5} F_n & \text{\(n\) is even} \\
- \frac{1}{5} + \frac{2}{5} F_{n + 1} + \frac{4}{5} F_n & \text{\(n\) is odd}
\end{cases}
$$
