How to solve linear recurrences consisting of both $x_n$ and $y_n$? 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?
 A: 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$. 
A: 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.
A: 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.
