# Solving recurrence relations with two variables

whenever I've had to solve recurrence relations, I've kind of just messed around with it until it works. I have a more complicated case, and I was wondering if there are general strategies someone could point me to for solving something like:

\begin{align*} a_n + b_n &= 2^n \\ a_n &= b_{n-1} \\ b_n &= 2a_{n-1} + b_{n-1} \end{align*}

With initial conditions $a = 0, b = 2$ for $n=1$.

Any help would be greatly appreciated. Thanks!

• Interesting problem! Are there initial conditions? – Andrey Kaipov Apr 21 '15 at 3:37
• Added the initial conditions – goodcow Apr 21 '15 at 3:44

with initial conditions $a_1=0$, and $b_1=2$.
By $(2)$, $a_2=b_1=2$, and now by $(1)$, $a_2+b_2=4\implies b_2=2$.
From $(2)$, we get $a_{n-1} = b_{n-2}$, so we stick that into $(3)$ to get $b_n= 2b_{n-2} + b_{n-1}$. This has a characteristic polynomial of $r^2-r-2=0$, so $b_n= k_1(-1)^n + k_22^n$. Since $b_1=b_2=2$, we can find the constants $k_1$ and $k_2$, and get $$b_n = -\frac{2}{3}\left((-1)^n + 2^n\right).$$
Notice that by $(1)$ we have $a_{n-1}=2^{n-1}-b_{n-1}$, and when stuck into $(3)$, we get $b_n=2^n-b_{n-1}$, which only requires the initial condition $b_1=2$ to solve. The solution is the same as the above, but it's nastier to solve since it's not homogeneous.
Now since $b_n$ is solved for, we stick into $(1)$ to get $$a_n = 2^n+\frac{2}{3}\left((-1)^n + 2^n\right).$$