<s>[INST] Derive a ϴ(1) formula for a Recurrence relation I'm given a piece wise function with sequence $a_0$ $a_1$ etc
$$a_n = \begin{cases}8 & n=0\\-7 & n=1\\25 & n=2\\7a_{(n-2)}+6a_{n-3}  & otherwise\end{cases}$$
I'm asked to derive a ϴ(1) formula for $a_n$, by solving the recurrence relation. 
I'm still learning about recurrence relations, so I'm wondering how to go about doing this.
Would I first try to find the given sequence for this piece wise function, and then find a formula from that? 
 [/INST] A generatingfunctionological solution is to define $A(z) = \sum_{n \ge 0} a_n z^n$, shift the recurrence by 3, multiply by $z^n$ and recognize resulting sums:
$\begin{align*}
\sum_{n \ge 0} a_{n + 3} z^n
  &= 7 \sum_{n \ge 0} a_{n + 1} z^n + 6 \sum_{n \ge 0} a_n z^n \\
\frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3}
  &= 7 \frac{A(z) - a_0}{z} + 6 A(z)
\end{align*}$
solve for $A(z)$ with the given values for $a_0, a_1, a_2$, as partial fractions:
$\begin{align*}
  A(z)
    &= \frac{8 - 7 z - 31 z^2}{1 - 7 z^2 - 6 z^3} \\
    &= \frac{4}{1 + z} + \frac{3}{1 + 2 z} + \frac{1}{1 - 3 z}
\end{align*}$
As this are just geometric series:
$\begin{align*}
  a_n
    &= [z^n] A(z) \\
    &= 4 \cdot (-1)^n + 3 \cdot (-2)^n + 3^n
\end{align*}$
</s>