1
$\begingroup$

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!

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

We're given \begin{align*} a_n + b_n &= 2^n \tag{1}\\ a_n &= b_{n-1} \tag{2}\\ b_n &= 2a_{n-1} + b_{n-1} \tag{3} \end{align*}

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

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