How can I solve this recurrence? 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.
 A: 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$.
A: 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.
A: 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.
