Solve the recurrence relation system $\begin{cases} a_n=-a_{n-1}-b_n \\ b_{n+1}=b_n-3a_{n-1} \end{cases}$ with $a_0=0$, $b_0=2$, $b_1=1$.
- First, I have a question about this: What's the intuition here? What
are we trying to solve? I mean like an example of a problem where we
can model the solution using recurrence relation systems.
What I've been doing:
I tried solving this as a "normal" system of equations.
$a_n=-a_{n-1}-b_n \iff a_n+a_{n-1}=-b_n \iff b_n=-a_n-a_{n-1}$.
So if $b_n=-a_n-a_{n-1}$ then $b_{n+1}=-a_{n+1}-a_{n}$
I plug both equations in the second equation:
$-a_{n+1}-a_{n}=-a_n-a_{n-1}-3a_{n-1} \iff -a_{n+1}+4a_{n-1}=0$
I end up with a second order recurrence relation, which makes no sense as the problem gives me only one initial term ($a_0$).
I stopped here as I can't solve $a_n$ with only one initial term…
Best Answer
You did well. You just stopped too soon! Now you solve $a_{n+1}=4a_{n-1}$, which is easy: $a_{2n}=0,a_{2n+1}=4^na_1$.
So from the first given equation $b_2=-a_2-a_1=-a_1$ and hence From the second given equation $b_2=b_1-3a_0=b_1=1$, so $a_1=-1$.
Now the first equation gives $b_{2n}=-a_{2n-1}=4^{n-1}=2^{2n-2}$ and $b_{2n+1}=-a_{2n+1}=4^n=2^{2n}$.
Check: $-a_{2n-1}-a_{2n}=-a_{2n-1}=2^{2n-2}=b_{2n-1}$
$-a_{2n}-a_{2n+1}=-a_{2n+1}=2^{2n}=b_{2n+1}$
$b_{2n}+3a_{2n-1}=2^{2n-2}+3\cdot2^{2n-2}=2^{2n}=b_{2n+1}$
$b_{2n+1}+3a_{2n}=2^{2n}=b_{2n+2}$
$------------------$
On your first question, I have no idea where this particular problem came from, but recurrence relations often appear when trying to solve combinatorial problems. Sometimes you get two different kinds of configuration mixed up, so it is convenient to denote their numbers as $a_n,b_n$ and derive relations like those in the Q.