How can I solve this recurrence?

Question

I have a weird recurrence relation and don't know how to solve it: $$a_n = pa_{n-1} + qa_{n+1} + cb_n$$ $$b_n = p'b_{n+1} + q'a_n$$ $$a_0 = 1$$ $p,q,c,p',q' \in [0,1]$ and $p+q+c=1,p'+q'=1$.

Thanks for help.

Answer 1

Here is a method for you to fill in some details:

You can obtain a linear recurrence in $a_n$ by using the first equation to write a formula for $b_n$ in terms of $a_n, a_{n+1}, a_{n-1}$. You can then use this to substitute for the terms in $b_n$ and $b_{n+1}$ in the second equation. The resulting recurrence can be solved using standard methods.

Choose to solve in $a_n$, because that makes it easier to use $a_0=1$ - it would also be possible to find a recurrence for $b_n$.

Answer 2

Try to use generating functions to do. Let $A(x)=\sum_{n=0}^\infty a_nx^n,B(x)=\sum_{n=0}^\infty b_nx^n$. Then \begin{eqnarray*} \sum_{n=0}^\infty a_nx^n&=&p\sum_{n=0}^\infty a_{n-1}x^n+q \sum_{n=0}^\infty a_{n+1}x^n+c\sum_{n=0}^\infty b_nx^n,\\ \sum_{n=0}^\infty b_nx^n&=&p'\sum_{n=0}^\infty b_{n+1}x^n+q'\sum_{n=0}^\infty a_nx^n. \end{eqnarray*} You can finish the rest.

Answer 3

Use "generatingfunctionology" techniques. Define $A(z) = \sum_{n \ge 0} a_n z^n$ and similarly $B(z) = \sum_{n \ge 0} b_n z^n$. Shift indices: $$ \begin{align*} a_{n + 1} &= p a_n + q a_{n + 2} + c b_{n + 1} \\ b_n &= p b_{n + 1} + q a_n \end{align*} $$ Multiply by $z^n$, add over $n \ge 0$ to get: $$ \begin{align*} \frac{A(z) - a_0}{z^2} &= p A(z) + q \cdot \frac{A(z) - a_0 - a_1 z}{z^2} + c \cdot \frac{B(z) - b_0}{z} \\ B(z) &= p \cdot \frac{B(z) - b_0}{z} + q A(z) \end{align*} $$ Given $a_0$, $a_1$, $b_0$ this is a linear system of equations in $A(z)$ and $B(z)$. Solve it, expand in partial fractions and you are set.