$$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$?
On
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} $$
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).$$