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$
  • $\begingroup$ What is "$\Theta(1)$ formula" supposed to mean? $\endgroup$ – vonbrand Feb 14 at 13:17
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$
  • $\begingroup$ What do you mean by "apply the given conditions for..." ? $\endgroup$ – user3739406 Oct 22 '15 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 '15 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 '15 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 '15 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 '15 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.