1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ What is "$\Theta(1)$ formula" supposed to mean? $\endgroup$
    – vonbrand
    Feb 14, 2020 at 13:17

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ What do you mean by "apply the given conditions for..." ? $\endgroup$
    – user3739406
    Oct 22, 2015 at 4:19
  • $\begingroup$ From the expression, express $a_0,a_1,a_2$ replacing $n$ by $0,1,2$ and get the equations. $\endgroup$
    – Claude Leibovici
    Oct 22, 2015 at 4:21
  • $\begingroup$ 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? $\endgroup$
    – user3739406
    Oct 22, 2015 at 15:21
  • $\begingroup$ 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$. $\endgroup$
    – Claude Leibovici
    Oct 22, 2015 at 15:32
  • $\begingroup$ Ahh yes I got it now, some basic arithmetic mistake (Seems to always happen with me in these courses). Thanks. $\endgroup$
    – user3739406
    Oct 22, 2015 at 15:34
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .