How to solve linear recurrences consisting of both $x_n$ and $y_n$?

Question

I know how to solve a general linear, homogenous recurrence but these are the ones I've been given:

(i) $x_{n+1} = 3x_n + 6y_n$

(ii) $y_{n+1} = 6x_n - 2y_n$

Initial conditions: $x_0 = -1, y_0 = 0$

How do I go about solving these?

Answer 1

There are a couple of ways.

Write the 1st as $y_n=(1/6)x_{n+1}-(1/2)x_n$, which also gives you $y_{n+1}=(1/6)x_{n+2}-(1/2)x_{n+1}$, and substitute these expressions into the 2nd equation to get a recurrence involving only $x$.

Or, rewrite as $v_{n+1}=Av_n$ where $v_n=(x_n,y_n)$ and $$A=\pmatrix{3&6\cr6&-2\cr}$$ Then $v_n=A^nv_0$ and you can work that out using the eigenvectors and eigenvalues of $A$.

Answer 2

Gerry is right, but there's a third way to do it, in which you determine the values of $a$ and $b$ so that $v_n=ax_n+by_n$ can be written as a recurrence only in terms of $v_n$.

So $$v_{n+1}=(3a+6b)x_n+(6a-2b)y_n = c(ax_n+by_n)$$ Therefore, $3a+6b=ac$ and $6a-2b=bc$. Elimiating $c$ gives $3ab+6b^2-6a^2+2ab=0$, and thus $6b^2+5ab-6a^2=0$, or $(3a+2b)(3b-2a)=0$.

Letting $3a+2b=0$, you have $a=\frac{-2b}3$, which means that $c=\frac{6a-2b}b=\frac{-4b-2b}b=-6$. Alternatively, you can use $3b-2a=0$ which gives $c=7$. Note that you can choose any number for $b$ in each case, so $b=3$ in the first one and $b=2$ in the second one makes sense. Then you'll have two separate first-order recurrence relations that you can solve separately, and then solve for $x_n$ and $y_n$ by basic algebra.

Answer 3

You can use Generating Function to solve this problem. Set $$ A(r)=\sum_{n=0}^\infty x_nr^n, B(r)=\sum_{n=0}^\infty y_nr^n, $$ and then from the recurrence, one can get $$ x_{n+1}r^{n+1}=3rx_nr^n+6ry_nr^n,r^{n+1}y_{n+1}=6rx_nr^n-2ry_nr^n. $$ Thus $$ \sum_{n=0}^\infty x_{n+1}r^{n+1}=3r\sum_{n=0}^\infty x_nr^n+6r\sum_{n=0}^\infty y_nr^n,\sum_{n=0}^\infty y_{n+1}r^{n+1}=6r\sum_{n=0}^\infty x_nr^n-2r\sum_{n=0}^\infty y_nr^n $$ and hence $$ 1+A(r)=3rA(r)+6rB(r),B(r)=6rA(r)-2rB(r). $$ Solving $A(r), B(r)$ from these two equations, one can get $$ A(r)=\frac{2r+1}{(6r+1)(7r-1)},B(r)=\frac{6r}{(6r+1)(7r-1)}. $$ Using Taylor expansions of $A(r),B(r)$, one can get the expressions of $x_n,y_n$ easily.