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?
On
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*}$
Just do it as usual $$a_n=7a_{n-2}+6a_{n-3}$$ which gives the characteristic equation $$r^3=7r+6$$ which has "obvious" roots $-2,-1,3$. So $$a_n=c_1 (-2)^n+c_2 (-1)^n+c_3 (3)^n$$ Now, apply the given conditions for $a_0,a_1,a_2$; this gives three simple linear equations in $c_1,c_2,c_3$.