# 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?

• What is "$\Theta(1)$ formula" supposed to mean? Feb 14 '20 at 13:17

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$.

• What do you mean by "apply the given conditions for..." ? Oct 22 '15 at 4:19
• From the expression, express $a_0,a_1,a_2$ replacing $n$ by $0,1,2$ and get the equations. Oct 22 '15 at 4:21
• Okay so i've gotten the 3 equations, and found values, tried to plug them back in, but they don't work. I tried using online calculators to find the 3 values, and they're all giving me errors, is there something wrong with this question? Oct 22 '15 at 15:21
• To me, everything is fine. Did you get $a_0=c_1+c_2+c_3$, $a_1=-2 c_1-c_2+3 c_3$ , $a_2=4 c_1+c_2+9 c_3$ ? If you did, there is problem to solve for $c_1,c_2,c_3$ for the value you are given $a_0=8$, $a_1=-7$, $a_2=25$. Oct 22 '15 at 15:32
• Ahh yes I got it now, some basic arithmetic mistake (Seems to always happen with me in these courses). Thanks. Oct 22 '15 at 15:34

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*}