How to find explicit formula for two recursions? I have to find explicit solution for two intertwining recursions
$$\begin{align}
f(n)&=f(n-2)+2g(n-1) \\
g(n)&=g(n-2)+f(n-1)
\end{align}$$
for $f(0)=1, f(1)=0, g(0)=0 ,g(1)=1$. 
What techniques are commonly used for this types of problem? Thanks!
 A: Hint: We can write this recurrence in matrix form as 
$$\begin{pmatrix}
f(n+1)
\\g(n+1)
\\f(n)
\\g(n)
\end{pmatrix}
=
\begin{pmatrix}
0&2&1&0\\1&0&0&1\\1&0&0&0\\ 0&1&0&0
\end{pmatrix}
\begin{pmatrix}
f(n)
\\g(n)
\\f(n-1)
\\g(n-1)
\end{pmatrix}$$
or more succinctly as $\Phi(n)=A\Phi(n-1)$. From this we observe that $\Phi(n)=A^n \Phi(0)$ where $\Phi(0)=(0,1,1,0)^T$. Hence this has been converted to a problem of linear algebra.
A: You can write $$f(n)=f(n-2)+2g(n-1)\\g(n)=g(n-2)+f(n-1)\\
g(n+1)=g(n-1)+f(n)\\g(n-1)=g(n-3)+f(n-2)\\g(n+1)-g(n-1)=g(n-1)-g(n-3)+f(n)-f(n-2)\\g(n+1)-g(n-1)=g(n-1)-g(n-3)+2g(n-1)\\g(n+1)=4g(n-1)-g(n-3)$$
And you have a single recurrence
A: One obvious technique that isn't obvious from the other two answers is to simply use one recurrence to eliminate one function from the other.
For example, the second recurrence gives $f(n) = g(n+1) - g(n-1)$ for every integer $n$, which can clearly be used (twice) to get rid of all occurrences of $f$ in the first recurrence, leaving a single recurrence.
