How does one solve this recurrence relation? We have the following recursive system:
$$
\begin{cases}
& a_{n+1}=-2a_n -4b_n\\
& b_{n+1}=4a_n +6b_n\\
& a_0=1, b_0=0
\end{cases}
$$
and the 2005 mid-exam wants me to calculate answer of $ \frac{a_{20}}{a_{20}+b_{20}} $. 
Do you have any idea how to solve this recursive equation to reach a numerical value?
 A: We can write the recurrence relation in matrix form
$$\begin{bmatrix} a_{k+1}\\ b_{k+1}\end{bmatrix} = \begin{bmatrix}-2 & -4\\ 4 & 6\end{bmatrix} \begin{bmatrix} a_{k}\\ b_{k}\end{bmatrix}$$
Hence,
$$\begin{bmatrix} a_{n}\\ b_{n}\end{bmatrix} = \begin{bmatrix}-2 & -4\\ 4 & 6\end{bmatrix}^n \begin{bmatrix} a_{0}\\ b_{0}\end{bmatrix}$$
Unfortunately, the matrix is not diagonalizable. Its Jordan decomposition gives us
$$\begin{array}{rl}\begin{bmatrix} a_{n}\\ b_{n}\end{bmatrix} &= \begin{bmatrix}-1 & \frac{1}{4}\\ 1 & 0\end{bmatrix} \begin{bmatrix} 2 & 1\\ 0 & 2\end{bmatrix}^n \begin{bmatrix} 0 & 1\\ 4 & 4\end{bmatrix} \begin{bmatrix} a_{0}\\ b_{0}\end{bmatrix}\\\\ &= \begin{bmatrix}-1 & \frac{1}{4}\\ 1 & 0\end{bmatrix} \begin{bmatrix} 2^n & n \, 2^{n-1}\\ 0 & 2^n\end{bmatrix} \begin{bmatrix} b_{0}\\ 4 a_{0} + 4 b_{0}\end{bmatrix}\\\\ &= \begin{bmatrix} -2^n & (1 - 2n) \, 2^{n-2}\\ 2^n & n \, 2^{n-1}\end{bmatrix} \begin{bmatrix} b_{0}\\ 4 a_{0} + 4 b_{0}\end{bmatrix}\end{array}$$
If $a_0 = 1$, $b_0 = 0$ and $n = 20$,
$$\begin{bmatrix} a_{20}\\ b_{20}\end{bmatrix} = \begin{bmatrix} -2^{20} & -39 \cdot 2^{18}\\ 2^{20} & 20 \cdot 2^{19}\end{bmatrix} \begin{bmatrix} 0\\ 2^2\end{bmatrix} = 2^{20} \begin{bmatrix} -39\\ 40\end{bmatrix}$$
Thus,
$$\dfrac{a_{20}}{a_{20} + b_{20}} = \dfrac{-39}{-39 + 40} = -39$$
A: Observe that
$$a_{n+1}+b_{n+1}=2a_n+2b_n=2(a_n+b_n)\;,$$
and $a_0+b_0=1$, so in general $a_n+b_n=2^n$. 
Quickly calculating a few values, we see that the numbers $b_n$ are a little nicer than the numbers $a_n$:
$$\begin{array}{rcc}
n:&0&1&2&3&4\\
a_n:&1&-2&-12&-40&-112\\
b_n:&0&4&16&48&128\\
\end{array}$$
Concentrating on the $b_n$, we see that
$$b_{n+1}=4(a_n+b_n)+2b_n=2^{n+2}+2b_n\;,$$
so that
$$\begin{align*}
b_n&=2b_{n-1}+2^{n+1}\\
&=2(2b_{n-2}+2^n)+2^{n+1}\\
&=2^2b_{n-2}+2\cdot2^{n+1}\\
&=2^2(2b_{n-3}+2^{n-1})+2\cdot 2^{n+1}\\
&=2^3b_{n-3}+3\cdot 2^{n+1}\\
&\;\;\vdots\\
&=2^kb_{n-k}+k2^{n+1}\\
&\;\;\vdots\\
&=2^nb_0+n2^{n+1}\\
&=n2^{n+1}\;,
\end{align*}$$
so $a_n=2^n-n2^{n+1}=2^n(1-2n)$, and
$$\frac{a_n}{a_n+b_n}=\frac{2^n(1-2n)}{2^n}=1-2n\;.$$
(There are other ways to solve that first-order recurrence for $b_n$; I just picked the most elementary one.)
A: A trick that is standard in my little world is this: the matrix
$$
M = 
\left(
\begin{array}{rr}
-2 & -4 \\
4 & 6
\end{array}
\right)
$$
has trace $4$ and determinant $4.$ The characteristic roots satisfy $\lambda^2 - 4 \lambda + 4 = 0.$ The Cayley-Hamilton Theorem (if this is not familiar, see the ADDENDUM) says that
$$ a_{n+2} = 4 a_{n+1} - 4 a_n,  $$ 
$$ b_{n+2} = 4 b_{n+1} - 4 b_n.  $$
It is easy enough to confirm these with direct calculations.
Because of the repeated characteristic value $2,$ we get $a_n = A 2^n + B n 2^n,$ with $b_n = C 2^n + D n 2^n.$
Calculating the first few of each to solve for the coefficients, we get
$$ a_n = 2^n - 2n 2^n, \; \; \; \; b_n = 2n 2^n. $$
ADDENDUM: 
Not everyone has seen Cayley-Hamilton. I did say it could be confirmed by straightforward calculation:
Suppose we have the system
$$ \color{blue}{   a_{n+1} = \alpha a_n + \beta b_n,}$$
$$  \color{blue}{  b_{n+1} = \gamma a_n + \delta b_n.} $$
We will find $a_{n+2}$ in two slightly different ways.
$$ a_{n+2} = \alpha a_{n +1} + \beta b_{n +1} = \alpha(\alpha a_n + \beta b_n) + \beta ( \gamma a_n + \delta b_n) = (\alpha^2 + \beta \gamma) a_n +(\alpha \beta + \beta \delta) b_n $$
Let me go straight to this, define
$$ \Psi = (\alpha + \delta) a_{n+1} - (\alpha \delta - \beta \gamma) a_n, $$
$$ \Psi = (\alpha + \delta)( \alpha a_n + \beta b_n) - (\alpha \delta - \beta \gamma) a_n, $$
$$  \Psi = (\alpha^2 + \alpha \delta) a_n + (\alpha \beta + \beta \delta)b_n - (\alpha \delta - \beta \gamma) a_n, $$
$$  \Psi = (\alpha^2 +  \beta \gamma) a_n + (\alpha \beta + \beta \delta)b_n.  $$
From
$$ a_{n+2} = (\alpha^2 + \beta \gamma) a_n +(\alpha \beta + \beta \delta) b_n $$
we find
$$ a_{n+2}  = \Psi,  $$
or
$$ \color{blue}{ a_{n+2}  =  (\alpha + \delta) a_{n+1} - (\alpha \delta - \beta \gamma) a_n.} $$
An analogous calculation works for $b_{n+2}=  (\alpha + \delta) b_{n+1} - (\alpha \delta - \beta \gamma) b_n .$
A: By adding the two equations you get
$a_{n+1}+b_{n+1}=2(a_n+b_n)$,
so that $a_n+b_n=2^{n}$.
Plugging this into the first equation one gets
$$
a_{n+1}=−4(a_n+b_n)+2a_n=-4\cdot2^n+2a_n,
$$
that is, dividing by $2^{n+1}$
$$
{a_{n+1}\over 2^{n+1}}=-2+{a_n\over2^n}.
$$
It follows that $a_n/2^n$ is an arithmetic progression and
$$
{a_n\over2^n}=-2n+1.
$$
