1

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.

kai
  • 25
  • 5
  • Your recurrence relation is not well defined as yet. You need 2 more initial starting values. Giving $a_1$ and $b_0$ would be helpful. – Calvin Lin May 10 '13 at 21:54
  • @CalvinLin On the other hand there is an obvious solution, which does make it possible to factor the cubic which emerges by providing an straightforward root. So there are more solutions than the obvious one. – Mark Bennet May 10 '13 at 22:02
  • If $p + q =p + q + c = 1$, then $c = 0$... – vonbrand May 14 '13 at 21:47

3 Answers3

2

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

Mark Bennet
  • 100,194
1

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.

xpaul
  • 44,000
0

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.

vonbrand
  • 27,812